Perhaps the key to looking at the two (越南 and 云南) is in "南" as these regions were all remote and to the south of most ancient Chinese empires/kingdoms.
There once was a kingdom called "越", which existed roughly from 2032 BC to 222BC (Baidu). It occupied most of eastern coastal areas of modern day China (you can see it on a map on Baidu-the 越 Kingdom is the bright yellow area labeled with a red character
https://baike.baidu.com/pic/越国/24727/0/b7003af33a87e950c7d9a59a19385343faf2b47e?) If you read stories from the Warring States era, you will encounter references to the kingdom of 越. In fact, at one point, one of the Kings of 越 took on another kingdom to its north (齐 Qi- roughly modern day Shandong Province), but failed to wipe out (齐)-which might have led to the demise of 越. By the way, in the same era (millennia), there were references to the existence of 东越 as well as 南越 -- 越 may be an ethnic name as well as a political (aka state/country) one.
Now could it be that the people who occupied 云南 were the same who also occupied 越南? Somebody may be able to dig out some historical documents to verify that. However, historically, 云南 had been called 南夷, "夷" being one of the many derogatory categorical terms used by ancient Chinese to refer to the "barbarians", aka non-Chinese. I am mentioning this because "越南" had been referred to by other names (other than "夷").
According to Baidu, the name "云南" came about in the Tang Dynasty when a Tang emperor asked an emissary from that region "where did you come from?" The emissary responded with a gesture "from the south, beyond the clouds." ("王问：君在何方？使遥指南曰：南边云下")