Jennifer,I could not locate a birth for John Paley in online records but it doesn't mean there isn't one.What I would recommend is to go to the nearest LDS(Latter Day Saints-Mormon)library and peruse the microfilms of the parish registers they hold.To give you an idea of where to look I found the following entries for Paley/Pally.
1796 Flaxgrowers Lists: James Pally parish:Ballymore county:Armagh
William Pally parish:Ballymore county:Armagh
Griffiths Valuation:1848-1864 Andrew Paley townland:Knockonny parish:Errigal/Keerogue county:Tyrone
Freeholders Lists: name:William Paley(note spelling change) residence:Crumore description of freehold:houses and land situate of freehold:Crumore value:£10. registered landlord:M Close from court session at Lurgan(co Armagh) June 1829
Pre-1858 Wills and Admons
index:Armagh Diocesean Wills surname:Paley forename:Thomas townland:Cruemore county:Armagh date:25 September 1830
Sadly this is all thats available info wise on these pre 1858 Wills and Admons.It does combined with the other info give you a place to start.The townland of Crumore/Cruemore in county Armagh seems to be where they are from.I did notice in the 1860's/1870's the name starts appearing in Dublin as well.I would concentrate in Armagh.If I come across anything else I will let you know.Hope this helps,Kim