I have taken a road trip to Newfoundland and it is a huge PITA with the ferry in terms of time and $$. If you have never been I would recommend it, but if you are looking to be on the road for 10 or so days I wound't bother. Stay in the mainland and NS and hop on over the bridge to PEI if you've never been there. I would take the Tans Canada Hwy there, but skip off of it when you get to Montreal and hop on Hwy 40 towards Trois-Rivieres and make a quick detour north to "La Mourice National Park". It is about 45 mins north and is a superb ride (I did this in a car and have been meaning to go back on my bike). You can make the loop and come back down to Grand Mere, take a nice scenic route to Quebec city, spend a night and hop back on the TC. Might be too much of a detour for you, but you will really enjoy it! QC is a beautiful province, the people are just pr!cks.
Here is a quick route that I've done up for you. Its something to consider.
https://www.google.ca/maps/dir/46.3...4,-72.879544,42082m/data=!3m1!1e3!4m2!4m1!3e0
As others have said, head back through the US. Much more scenic and enjoyable compared to the TC and it will be a new ride back for you also