you think of crossing the pacific, but a less daunting way would be follow the westcoast of the americas all the way from the south to the Aleutian islands in the north, and follow the coast from there.
So the question would be whats the earliest time this coast hugging circumnavigation is possible.
So from a european point of view a route like this:
Portugal - Canary islands- Brazil - point of south america - aleutians - china - india - Aden - following africa to the cape - then all the way back up to europe.
or from china:
china - india - Aden - following africa to the cape - west africa - brazil - point of south america - aleutians
(or reverse route: aleutians - cape H.- brazil - caribean - us east coast - iceland - uk/ europe - down africa etc, different route is result of the gulfstream)
or variations on this
in the case of of the chinese they could have discovered the americas early, but they lacked the political will for it.
I agree with the others that Cape Hoorn/Magellan straits are the biggest obstacle, if someone ends up landing (or a colony) somewhere in latin america, i could imagine a landcrossing there and continue the seatravel on the other side
Edit: An early circumnavigation would likely not be the roundtrips from otl, but think more of an epic 10 year odyssey.
What would be the chances of an early round the world triP? so not just being naval, maybe take a caravan overland in eurasia, bit like marco polo squared/ early version of around the world in 80 days(10 years in this version)