Here's the recent timetable of flights from Odessa. You can see that other options include flying a very old turboprop AN-24 on Ukrainian National Airlines to/from Zhulyani (small airport close to downtown Kiev), or once-a-week B-737 flight to/from Boryspil (Kiev international airport) on Aerosweet.

With all due respect, I have to disagree with FlyingRev on the train travel issue. I've traveled very extensively by train between major cities in the former Soviet Union, and as long as you're buying 1st Class (called "SV", 2-bed compartment) ticket on a flagship train (hint: the lower the train number, the better quality of service), you should be fine. Safety-wise, make sure you securely lock your compartment at night (you may want to invest a few bucks in buying a special additional lock, they are sold at major railway stations).