Have you found your Richard on the Canadian Census returns ?
I see a few people of that name on the 1861 and 1871 census - those I checked were Church of England (Anglican) or Methodist. Knowing the denomination of your Richards family could help narrow down any likely church records.
Church records for most Catholic parishes in Ireland are available on the (free) National Library website the name of the Catholic parish for the areas in Camolin. There are some Church of Ireland records for Co. Wexford on (pay-website) RootsIreland, unfortunately they dont have any for Ballycanew Church of Ireland parish so far. According to the latest parish list from the RCB Library baptism, marriage and death/burial records for Ballycanew Church of Ireland parish go back to 1733 and available on MicroFilm in the National Archives in Dublin. The original registers are most likely still held by the parish.
The Tithe Applotment Records, which cover those with certain types of agricultural land, shows a number of entries for people with the surname Richards in Co. Wexford, including one in Ballycanew civil parish - a Francis Richards (see item 92 in the image) with a small holding in Ballycanew townland near the village. This section of the Tithe records is dated 1st July 1833.
There was no Irish Army at that time, the '39th Foot' would be a British Army Regiment and seems to be reference to the 39th (Dorsetshire) Regiment of Foot (Wikipedia), which served in several locations abroad including Crimea, Canada & India.