We went the opposite direction, from Odessa through Moldova, last summer. We didn`t have a visa so we bribed our way through. If you get stopped by the police (and you will) expect to pay! Not much though, we never paid more than 10USD for the "fines". Bring small USD or Euro bills, usually 2-5 EUR will get you off the hook.It`s the same in Ukraine. There were miltary checkpoints all over, but we never experienced it as dangerous. We meet two Germans in Odessa, they had similar problems. Overall we found the police very polite and friendly, so the curruption doesn`t feel "unpleasant".
Ukraine and Moldova is wonderful, but poor. Your bike will attract interest, but positive. Be carefull about speeding, the police have plenty of controls and radars.
Most hotels have guarded parking lots, so your bike is quite safe. You pay for this in addition to the hotelbill. I wouldn`t park it on the street however!
Good luck and have a nice trip!