I did little research in Kutaisi, Georgia in person.
Registration of the company can be done in one day by going to Public Service hall (consider it something like combined service point for all government services). Cost of registration, 100 GEL (about 32 euro) or double if you want the registration to happen immediately.
Paperwork will be in both English and Georgian, but you still need a translator to translate the forms you sign (which are in Georgian), however the translator doesn't have to be certified (=any friend will do).
However, the biggest problem seems to be that you need permission from the owner of︀ the real estate for the address you are going to use in registration. I was︁ not able to find any reasonable service providers for this. I heard flat owners can︂ do this if you sign long term lease. I also found couple of companies in︃ Tbilisi, but their prices were rather high.
Even if you hire translator, registration process is︄ really cheap and quick.