Pick up a SIM in the first EU-member country you visit. In Ukraine, either pay whatever they charge, go without a SIM for a few days (i.e. cache the map and only make phone calls over wifi), or buy something there if you really need. Your trip is less than a month, so just buy a month of whatever you need and call it good.

PAYG SIMs are affected by the EU telecoms rules just like postpaid SIMs; there are a few (mostly Baltic) providers with exceptions and a couple fly-by-night providers who still think the rules don't apply to them but for the most part every EU SIM works like at home in every EU country other than the 9GB/mo data limit for plans that offer more than that in their home country.

For calling back to the US, you pay the international rate, and it's bound to be obscene. Think €2.50/minute. You've got a smartphone, so why not set up a Google Voice number and make free VoIP calls to the US and Canada with the Hangouts app? (this is one of the many reasons smartphones are better than the old flip phones...)