First of all, this is Ukraine. A hotel may have some foreign guests but still, the majority of them would be Ukrainian or Russian speaking. The fact that you only speak English makes a hospitality job unsuitable for you.
No. You cannot change to a working visa from a visitor visa or on a visa-free entry. After you find an employer willing to sponsor you, you have to exit Ukraine first to get a D visa and then come back.
Put yourself in a potential employer's shoes. Why should he bother with a foreigner who requires extra work for him, ie. visa sponsorship, unless you have a special skill that is hard to find and your deficiency, ie. no Russian or Ukrainian, doesn't impact your job performance?
With that said, if you are not in IT, science, medicine, etc. ie. a trained professional, or you don't want to teach English as a native speaker, it's not likely you can get a job unless you want to compete for a low-level job that even the locals don't want.
Speaking of a low-level job, even if an employer wants to hire you, it's not likely the government would approve it! So your employer is hiring you because he wants to exploit you like a slave. Your visitor visa would soon run out, and you will end up in Ukraine as an illegal alien. In this case, you need to do some soul searching why you bother to come to Ukraine.
This is not unique in Ukraine. Most governments/ employers don't want to deal with foreigners unless they bring something significant to the table. If I look at the situation back home in the U.S., a foreign worker is often either a "rocket scientist", so to speak, or a slave, i.e illegal alien! Sure, we also have foreign-born workers that are mediocre, but these people either got their Green Cards through their families or as political refugees, ie. they do NOT need visa sponsorship, but STILL MOST OF THEM SPEAK THE LANGUAGE.
