Here is the 1851 Census that shows him in Sidney, Hastings, Canada West.
He is listed as age 55 (makes his year of birth about 1797), born Ireland, Catholic. He is the last entry on the page and there is no X to indicate he is married; this makes sense because Mary isn't born until 1854, so I would estimate a marriage date for Arthur and Elizabeth at about 1852 or 1853. Additionally, he is the only Donnelly enumerated in Hastings County in 1851, so if he immigrated with anyone, they aren't living close by.
Unfortunately, I think this is a brick wall. There weren't really any census records before 1851, marriages were not registered until 1869, and although you can find some county registers, they don't start until about 1858.