If you're strictly looking at Star Alliance: from Canada in the past, I've had good luck on Turkish Airlines which fly to Hanoi and Saigon from Istanbul in something of a triangle (some days it is IST-HAN-SGN-IST, and others it is IST-SGN-HAN-IST, so if you're flexible on your days you may get lucky.) I've used Aeroplan for those before, though I'm not a fan of the Turkish Airlines business class product at all, and Aeroplan has become all but useless lately in my opinion. If you're more into oneworld, I've had friends spend BA Avios flying from Montreal to Saigon via Doha on Qatar.
My advice: see if you can make it as far as HKG, SIN, KUL or BKK and then buy the last flight separately. Those airports are bringing in many A380s and 777s full of premium seats from all over the world, but then putting people on A320s and 737s for the last hop to Saigon. SGN is a much, much smaller airport that doesn't see the number of big planes like those other 4 airports.
My other advice: also look at entering Vietnam through Hanoi or (increasingly) Da Nang.