Sounds like a great trip, though being a lazy tike I'd probably fly the odd sector and allow a bit more time hanging around in one place for a few days/week.

I only really know Vietnam well and have never been to Laos. A number of my friends have entered Laos overland from Vinh in Vietnam.

So a change people might wish to comment on is for you to do:

SIN-HAN
Hanoi (inc side trip to Ha Long Bay, maybe Sapa)
Hanoi to Vinh (train or bus, including Ninh Binh, Tam Coc - especially if you didn't do Ha Long Bay)
Overland to Laos
Back to Vinh and continue south to HCMC (Saigon) - Hue, Hoi Anh, Nha Trang etc
Mekong delta, chill out on Phu Quoc (can go by sea...)
Cambodia
REP-SIN

Not sure how keen you were on the train ride BKK to Nhong Kai you mentioned.

Bear in mind most tourist visas to Vietnam are single entry, one month. You can extend, get another entry, or both once inside Vietnam without hassle. (You need to be in the same place for 2 or 3 days.) OR you can arrange a longer visa in advance.