When did Japan and the Three Kingdoms of Korea first meet?

In terms of recorded history, the earliest contact that I know was in 50 B.C., when a Japanese army supposedly aborted its invasion upon hearing of the Silla king's greatness. Make of its credibility what you will...

《三國史記·新羅本紀》八年，倭人行兵，欲犯邊，聞始祖有神德，乃還。

This is recorded in the History of the Three Kingdoms, written in A.D. 1145. The same document reports sporadic skirmishes with the Japanese until the second century, when contact (including envoys) became more regular.

Actual first contact is arguably much older than the earliest records, because the Japanese people partially originates in Korea. This theory argues that the Yayoi people, who brought with them rice cultivation, migrated into Japan from the Korean peninsula and intermingled with the preexisting Jomon population (who are closer to the modern Ryukyuans and Ainu) to form the modern Japanese.

There have been at least two major migration events that brought modern human populations from the Asian continent to the Japanese archipelago. The Jomon people arrived in Japan >10,000 years ago ... the Yayoi, originally from northeast Asia, started migrating to Japan from the Korean peninsula -2,300 years ago.

_{- Hammer, Michael F., and Satoshi Horai. "Y chromosomal DNA variation and the peopling of Japan." American journal of human genetics 56.4 (1995): 951.}

The arrival of the Yayoi marked the beginning of the Yayoi period, conventionally dated to c 500 B.C. based on archaeological remains of rice. Since the end of the century however, then there has been a number of discoveries, which seemed to have pushed the start date back closer to 1000 B.C. or so.

This is probably less "when they first met" and more "when they first separated".

Contact between Korea and Japan became more regular from the start of the fourth century or so. Archaeological evidence indicates a large amount of materials passing between Korea and Japan from around this time.

For instance, there is much archeological evidence that people and material objects passed between Japan and Korea in the period a.d. 300 to 700. Japanese interpret this to mean that Japan conquered Korea and brought Korean slaves and artisans to Japan; Koreans believe instead that Korea conquered Japan and that the founders of the Japanese imperial family were Korean.

_{- Diamond, Jared. "Japanese Roots." Discover Magazine 19 (1998): 86-95.}

Japan had, in the fourth century, became a more unified polity. This led it to begin seeking from Korea (which was its nearest continental neighbour) resources and technology, such as metal for farm instruments. But the ensuing trade encompassed much more.

Scholars ... have shown that the peninsular peoples transmitted a huge volume of materials, technologies, ideas, and institutions to the archipelago. These items included: iron and iron-working techniques, iron weapons and armor, horse trappings, new agricultural tools and practices, stoneware, the household oven, gold and silver metallurgy, stone-fitting methods, silk-weaving, writing, plans for mountain fortifications, the crossbow, Buddhism and its architecture, and methods of statecraft such as the be, kabane, law codes, and ranking.

Peoples of the Korean peninsula acted as middlemen, often altering or refining ideas that originated elsewhere. Four mechanisms encouraged the influx: minimal trade, large-scale immigration, some plundering by Japanese troops fighting in Korea, and the foreign policies of states such as Paekche and Koguryŏ.

_{- Farris, William Wayne. "Ancient Japan's Korean Connection." Korean Studies 20.1 (1996): 1-22.}

This trade coincides with a growing occurrence of Japan in Korean records, and vice versa in Japan's. The Seven Branched Sword, which is believed to be the same artifact that featured in the Chronicles of Japan as a gift from Baekje to Empress Jingu also dates to around this time.

Wikipedia's "close relationship at the end of the 4th century" is probably talking about Yamato Japan's alliance with Baekje. That began in A.D. 397, and precipitated in a war with Goguryeo. This is recorded in several ancient historical records of both sides. Additionally, it is attested to in the contemporary Gwanggaeto Stele, which commemorates King Gwanggaeto the Great who reigned in Goguryeo during the conflict.

The exact details is somewhat subject to debates, often with nationalistic overtones (one North Korean scholar apparently claims that Gwanggaeto conquered Korean colonies in Japan). But generally speaking, it is usually thought that Goguryeo had subjugated Silla and subdued Baekje. The latter then forged an alliance with Japan to attack Silla and Goguryeo, but the coalition was defeated by Gwanggaeto's forces on both attempts.

According to the History of the Three Kingdoms, between A.D. 397 and 405, Baekje's Crown Prince Jeonji was hostage in Japan. Envoys were recorded to have been sent between the two courts in 402, 403, 418 and 428, but became more sporadic afterwards in the records.

《三國史記·百濟本紀》 六年，夏五月，王與倭國結好，以太子腆支為質。

This alliance was maintained until A.D. 660, when Baekje was conquered by Silla and the Tang Empire. Upon request by Baekje loyalists, Japan sent an expeditionary force to help restore Baekje independence, but it was annihilated in 662 during the Battle of Baekgang. Afterwards, Japan resettled the Baekje remnant within the Japanese isles and retreated completely from the peninsula for the next 900 years.

_{Disclaimer: This section presents a very controversial idea, and I am not claiming it is correct by any means. However I find it interesting and felt it worth mentioning.}

It has been suggested by some that the Gaya Confederacy in southern Korea was a Japonic state (or even more provocatively, a Japanese outpost) recorded in Japanese records as Mimana. Part of the evidence put forward for the claim is some apparently Japonic toponyms in the peninsula and the Gaya language.

A version of this theory argues that Gaya was a Japonic remnant left on a peninsula, after the general Yayoi migration to Japan. It has also been argued that this Yayoi remnant was Buyeo, from which Baekje claimed descent.