I've wondered about that myself. Ezo would have been a perfect place from which to trade both with Japan and with the Jurched as they were becoming Manchu. It is not choked by ice. It is occupied by no one in the 16th Century. And the Ainu, while strong enough to deter casual conquerors are not against traders. The question is who would bother to go that far north in East Asia and why?
The Portuguese almost got there. They got as far as Sendai, where the Date Daimyo converted to Christianity, but no further. They eventually settled on Nagasaki.
In fact the Dutch and the English, their major rivals, settled on Nagasaki too. For some reason, probably having to do with concentration at Guangzhou (Canton), European merchants in Asia at this time all preferred to be in the same city. Even the English refused the very lucrative opportunity to locate their trading factory at his fief of Miura, preferring to build it at Hirado, across from Nagasaki, near the Portuguese, Spanish and Dutch. (And indeed the Dutch did endure, keeping a low level presence at Deshima even after Japan's seclusion policy until 1853).
Russia?
Russia got to the Pacific Ocean late, after 1630, after Japan closed Ezo off to foreign trade.
Spain might be the best bet. Here is a scenario that might work.
Magellan's flagship Trinidad sailed from the Molucca Islands attempting to reach Mexico with a load of cloves that could be transshipped to Veracruz and on to Spain. After sailing north of Guam, and reaching close to the Westerlies, the Trinidad sprung leaks and her pilot decided to return to I believe Ternate, where the Portuguese, by then alerted to the presence of Spanish, captured and killed all of the crew OTL.
ITTL, the Pilot or Acting Captain makes a different decision and veers west to Japan, making landfall around Hachinohe or Aomari on the Tsugaru Strait. The Captain is able to convince the Daimyo of the value of cloves and with the help of a silk merchant who understands what cloves are worth on the Chinese market to Chinese who are marketing the silk Japanese wear (as well as the Portuguese), are able to trade some cloves for gold at a reasonable enough rate to finance the ships' repairs. The Trinidad goes on it's way (with among other things, durable silk sails and some of it's cargo converted to silk) and proceeds to visit the island of Ezo to the north before proceeding east. At Ezo, Trinidad finds some furs to go along with the silk, so with a more diverse cargo and plenty of food, including fruit and green vegetables, Trinidad sails east in 1538 and after 9 weeks, makes landfall near Nootka Sound.
After discovering what would be Puget Sound OTTL, Trinidad travels south along the North American West Coast, disappointed that Puget Sound was not the Strait of Anian, past what would be the Columbia River (partially blocked by a sandbar) discovering harbors at Willapa Bay, Grays Harbor, Coos Bay, Humboldt Bay, Bodega Bay (San Francisco Bay is socked in by fog), Monterrey Bay and San Diego Bay, finally reaching Acapulco.
As a result of this discovery, Ezo is seen as a strategically located island, critical for Spain's Manila Galleon route and North America's West Coast is seen as a potentially rich source of valuable furs if not necessarily gold (gold is later found too).