From Sofia to the West of Turkey should be relatively easy. After that, travel through Iran, Afghanistan and Pakistan will get hairy.
Source: me and my wife traveled extensively by public transport in, well, at least Pakistan. The other countries are indeed sort-of hairy, but mostly for job-clearance-related reasons.
1. https://en.wikipedia.org/wiki/Balochistan_Liberation_Army