Welcome to Ireland Reaching Out!
The RC records for the parish start in 1838 http://registers.nli.ie/parishes/1051 but unfortunately the baptismal records for this parish are not on Roots Ireland. Which means you may have to scan the register in the 1840s to see if you can locate a record for Patrick. The only place I can locate with Costello would be Costellopark in Monivea civil parish Monivea is a good deal south of Templetogher. I checked the 1855 Griffiths Valuation head of household listing for Monivea parish and there were no Cady or Cody records.
I did check the 1855 Griffiths Valuation head of household listing for Templetogher and there were three Heavican/Hevican reocrds. Possibly one was the father of Patrick.
Have you considered autosomal DNA testing?