I planned this route 2 years ago.
Constanta LRCK had avgas, customs, and some GA presence/services.
Odessa UKOO had no avgas, but had customs.
I was planning to fly Crete LGSA - LRCK - UKOO - LZKZ (Kosice, Slovakia, which had avgas and customs).
That route was abandoned the night before due to complicated Eurocontrol routing issues. I don't know about VFR but it should be OK.