If Matthew was of Scotch-Irish descent then he?s probably Presbyterian. Your main problem is that there are very few Presbyterian church records for the 1700s in Ireland, and without having some idea of where he came from, it?s a needle in a haystack (plus there may be no records to find anyway).
Looking at the 1901 Irish census (the earliest complete census) there were 5049 people named Bradley in the country. 4183 were RC. Just 206 were Presbyterian. As you might expect, given the history of the Plantation of Ireland, the vast majority of those were in 5 of the 6 counties which now make up Northern Ireland. So your belief that Matthew originated in Northern Ireland seems sound. In this case there were Presbyterian Bradleys in: Antrim, Armagh, Derry, Down & Tyrone. None in Co Fermanagh.
But that?s still an enormous area. Without some clue from US sources as to where they originated, it?s not really possible to give you any suggestions as to how to trace them that would of any real value. If you narrow them down to a parish or townland, I can tell you what records exist for that area but otherwise it?s pretty hopeless.
If Mathew?s family were Scotch-Irish, then typically they will have arrived in Ireland in the 1600s. They arrived throughout that century from about 1606 onwards but there was a particularly big rush in the 1690s, due to famine in Scotland. So your family may only have lived in Ireland for 2 or 3 generations before leaving again. (That was a very common scenario).
DNA testing might be your best bet, both for finding any living relatives in Ireland but also in Scotland.