Well, it's a big area, and I'm sure you don't want to spend your time driving. :)
Kouchibouguac is coastal, low elevation, barrier islands…all dunes and salt marsh, beautiful but no really long loop trails. More restful than challenging.
Bay of Fundy National Park, however, lets you link up trails into a 48 km loop through all kinds of habitat. Google 'Fundy Circuit'. Might be perfect for the time you have.
If you come down into Nova Scotia, Kejimkujik has the 60 km 'Liberty Lake' loop around the park, a fairly rugged hike, though not much elevation. Can be muddy. Lots of wildlife, so beware trail confusion. Bring your DEET! Keji is also a 'dark sky preserve' and will be fantastic for the Perseid meteor shower in the next few days.
The Cape Breton Highlands are where you'd go for elevation (although Newfoundland has higher hills by far). The trails are shorter, however, and you'd have to do some work to put together a true backcountry route.
You'd be a couple of days just getting to Newfoundland, so sadly we might have to leave it out. You'll just have to come back. :)
Edit: I misremembered Keji's loop distance, it's 60k, not 50.