Emperor Simeon is actually asking more of a trick question and a toss-up than one might think. True, the Americas may be marginally geographically closer to Constantinople. But you're talking constant trade winds in a direction that nobody in Rhomania knows that there is anything to find. And the ships on the Mediteranean are predominantly dromans and galleys--oared ships ill suited to crossing the Atlantic without their oarsmen dying of dehydration. Then the problem of the return voyage. Rhomania will need to take over Scandinavia before it will have the knowledge that there may be some sort of Terra Nova to the west of it on the Atlantic.
Wheras the axis of trade for Rhomania extends down the Red Sea to the Gulf of Aden and the Indian Ocean. Where Rhomania will soon reach not only India but Srivijaya and the Spice Islands. And the north coast of Australia.
Now the north coast of Australia is not suitable for colonization by anybody until modern times. But Rhomanian traders are also trading down the east coast of Africa and will probably go all the way to Natal if not the Cape. And in the Indian Ocean, traders use lateen rigged sailing ships, not oared ships and do sail the open sea. Because they understand the monsoon winds.
It's a lot easier to be willing to take some risks if a) you have a smaller crew and are used to staying out of sight of land for a few weeks on end and b) you have some idea where you're trying to get to. Rhomanian Indian Ocean traders who do not wish to wait for the monsoons will soon discover that if they sail far enough south, there are easterly trade winds that can take them directly from Srivijaya to Madagascar or Africa. The Malagasy can tell them all about them when they get to Madagascar since those are the winds that brought THEM there. They will also notice, sailing farther and farther south, looking for things like ivory, that when they get to about 32degrees south, the winds shift to westerlies and if they put in, the rains fall in the winter, just like they are used to, and wheat will grow in the farthest south of Africa. From there, attempting to use those Westerlies, it would be a simple matter to try to sail due east and try to turn north at the right time by dead reckoning to reach Srivijaya with a load of elephant tusks and lion and leopard skins, maybe ultimately bound for Serica via Lombok Strait. Only they bump into Southwest Australia where they find water from the OTL Swan River, "standing deer" to catch and skin and bring in live as curiosities, maybe a few platypuses and/or Koalas and some fruit to ease their scurvy after 8 weeks at sea. Then on to Bali and Zhongguo for a load of silk and a return voyage via a more conventional route.
Which is a voyage I suspect is likely to be completed a lot sooner ITTL than one to North America, and one much more likely to result in a colonia. Since the people attempting it actually have some idea where they are going and where they want to go. As long as they aren't blown off course to the south by a storm (in which case they could be shipwrecked on the Coorong

or have to make their way past Tasmania or the Bass Strait and the long way around Australia

) .Law of averages, people will get through it OK and word will get out about Australia. And eventually, gold will be discovered.
