Columbus letter to the sovereigns of Castille Luis de Santángel, as I talked about here, was an instant hit and was widely reprinted and translated across Europe. No fewer than eleven editions in first year following the return were published. Of course, the letter didn't mention anything about New World, but talked instead about finding new islands of the edge Asia, as at that point Columbus still hadn't realized he stumbled upon something new.

As I explained here, this "New World" realization was made in circa 1502, when two works (Mundus Novus and Four Voyages) attributed to Amerigo Vespucci (modern historians think it is likely that the works were garbled and compiled by someone else from authentic Vespucci letters, under his name) were published and began circulating through Europe. The works explicitly reference the existence of previously unknown landmass (South America) and more importantly, were smashing hits throughout Europe. Rudolf Hirsch in his article 'Printed Reports on the Early Discoveries and Their Reception' counts three times more different editions of Vespucci's work (more than 60) than Columbus' in the first 30 years following the discovery, as well as much more translations to vernacular languages. Which kind of explains why German cartographers went with Vespucci's name for the new landmass rather than Columbus, when since (at latest) 1507 they started including the new continent(s) on the maps.

From Christian Europe word spread to the rest of the Old World. Ottoman empire had a large presence in the Mediterranean through trade and piracy, and was quick to get news of the New World. Piri Reis published a Ottoman map in 1513 which shows New World, and on which he directly states he copied and used Portuguese and Spanish maps to compile. From the 'Off the Edge of the Map: The Search for Portuguese Influence on the Piri Reis Map of 1513' by Shaw Bridges here's the translation of the inscription from the map:

From about twenty charts and Mappae Mundi – these are charts drawn in the days of Alexander, Lord of the Two Horns, the Arabs name these charts Jaferiye – from eight Jaferiyes of that kind and one Arabic map of Hind, and from the maps just drawn by four Portuguese which show the countries of Hind, Sind and China geometrically drawn, and also from a map drawn by Qulunbu [Columbus] in the western region I have extracted it. By comparing all these maps with one another, this final form was arrived at. So that the present map is as correct and reliable for the Seven Seas as the map of these this country is considered correct and reliable by mariners.

For South and South East Asia we have less reliable ways to date the arrival of this information as i talk about here. It is highly likely that it was transmitted with the Portuguese arrival to the region. The news could have been conveyed through diplomatic and trade activities, through captured soldiers or renegades who turned sides, through numerous ambassadors and dignitaries who were sent to Europe and back, as well as slaves and captives who might had unwillingly done the same trip. In an effort to pinpoint at least some year, we can give year 1512 when the Portuguese governor of India Afonso de Albuquerque mentions seeing a Javanese map that shows among other things coast of Brazil. There is some serious debates on what this statement actually meant (as the map doesn't survive) but shows the strong likelihood that the new geographical knowledge was quickly disseminated and incorporated in Southeast Asia.

For China and Japan we have less evidence of exact date of exchange. Portuguese had contact with China since at least 1517/1518, before the outbreak of hostilities in 1520s following the Emperor's death, when Chinese also imprisoned an embassy sent to the royal court, which they could interrogate but we have no idea if they did. I talk about Portuguese early contact with China here. The first official mention I could find of the existence of New world, was in 1581 when Jesuit Matteo Ricci arrived to Beijing. In the official History of the Ming Dynasty (taken from Zhishan, Zhang. “COLUMBUS AND CHINA.” ) we have this passage:

During the Wanli Reign, a man of that country, called Li Madou (Matteo Ricci), came to the Capital. He presented a map of the world, stating that there are five continents... . His narration appears strange and indistinct, and can-not be checked. But since a man of that country came all the way to China, we should not deny its importance

For Japan we have a similar situation of unknown. As talked here Europeans had direct contact with Japanese from 1540s, during which Jesuits could have easily spread knowledge of the New World, not least since the Spanish arrived in 1560s to the Philippines by Manila galleons from Mexico, and soon sent envoys to Japan as well. At least one Japanese embassy, in 1613-1620 went to Spain and back to Japan via New World, but was preceded by a number of Filipinos, Chinese and Japanese unofficial migrants reached Mexico via the galleons before that.