The 1870 marriage certificate states that John’s father was Patrick D, farmer. Your information is that he came from Cullyhanna.
Looking Griffiths Valuation for 1864 there is a Patrick Donnolly farming in Cullyhanna Big. He had plot 8, a 6 acre farm. The Valuation Revision records on the PRONI site show him remaining there till 1898 when he was replaced by Beth Quinn.
Cullyhanna Big is in the RC parish of Creggan Lower. Their baptism & marriage records start in 1845. Have you checked them for John’s baptism (which might just scrape in), to perhaps confirm his parents names from that? You might also find any siblings born after 1845. But getting back much further than that will prove tricky due to the absence of church records.
The tithe applotment records for 1828 do list a Michael Donnelly farming in Cullyhanna then, so that’s a hint that it could be Patrick’s father. But there’s no certainty to that.
There was a Mary Donnelly in Griffiths in a labourers cottage in Cullyhanna Little in 1864. Could that be a relation?
Have you searched for gravestones in the local churchyards?