My current choice of places is:
Hong Kong
Singapore
Malaysia
Thailand
Indonesia
Phillipines
Myanmar or Cambodia (I don't think I'll be able to spend many bitcoins in these two places)
It would be especially great if I could pay for the whole trip with Bitcoin, including flights/hotel/bar/restaurants...
Where would be the best place to go?
Are you going backpacking?
I've been to Malaysia, Thailand, Indonesia and Cambodia of the places you're looking to visit. At the time Bitcoin wasn't prevalent, and I don't think it would be easy to do all your spending in Bitcoin even today. You'll likely need to have local currencies, except in Cambodia. They seem to be quite happy accepting US dollars.
If you're going backpacking, I'd recommend starting in Thailand. It's the easiest way to transition into backpacking lifestyle, meet lots of other backpackers, and Thailand is very well setup for backpacking. Most people speak English so there's little language barrier.
Enjoy your travels
Thanks, no I'm not backpacking - I'm currently based in Vietnam and I need to renew my visa, so I thought a trip to another country close by would be cool, rather than the bus to the Moc Bai border with Cambodia.
I am planning on doing some travelling soon though, and Thailand is high up on my list. I absolutely love Thai food so that is a big factor!