John Paton was born well before the start of civil registration in Ireland and it's also quite early for records of most churches so there might be little detail on him here (let alone his parents).
In order to see if church records do exist then you'll need to know the family's religion at that time and where they lived (parish if not actual townland).
Have you checked Australian records for clues? marriage and death certificates, assisted passenger lists (as was found on another query of yours), etc.
