I recently upgraded form an 8600k to a 9900k.
If your cpu is at stock or even underclocked as you seemed t have stated, those temps are not normal.
Here is what I observed on my chip and board.
I flashed the bios, installed cpu and cooler, my cooler is an air cooler the noctua nh-d15s in single fan configuration, fan speed set to performance in bios (still dynamic speed but more aggressive ramp up.
Observation immediately was the very high voltage, vid was 1.52v simply running bench in cpuz, and vcore was around 1.36v. Even in this configuration the temperatures were slightly better than my 8600k. After a little research I figured out that the board vendors are massively overvolting these chips, and reduced it to a fixed 1.25 vcore. This reduced temperatures depending on load around 15C which is pretty significant, I them bumped the clocks to an all core 4.8 which it can still handle at 1.25v so I probably could have reduced voltage even more in stock configuration.
The cpu is now one of the coolest cpu's I have owned, I was playing FF13-2 yesterday and during the game with my heating on the cpu temp was average 40-43C which is really really nice. Running at 4.8ghz all cores.
During a stress test such as XTU benchmark which is a very demanding AVX test, the cpu peaks in the high 60s, which is for me a very good temperature for a modern cpu, realbench starts out in the low to mid 60, but it creeps up during the run, and ends up in the mid to high 60s, that suggests to me I have a air circulation issue in my case, so thats my problem to fix, but still massively better than my 8600k, which averaged 60 or so in games and 80-90 in tress tests.
This is the same case, same psu, same ram, same board, same OS, as my 8600k, I did a cpu swap basically, cpu cooler was swapped tho from a cryorig R5 to the noctua which no doubt has helped, but the 9900k is performing well for me without any kind of water or AIO cooling.
So my first suggestion would be to look at those voltages, and not just vcore, I also reduced VCCPLL, VCCIO, and VCCSA, all 3 get pumped too high by the board vendors, especially if you enabling XMP for the ram.
Also adaptive voltage has issues with going too high under load, it has advantages when idle, but those advantages are not that big anymore, with adaptive my 9900k sat idle on the desktop at around 24-26C, on fixed vcore its now 28-30C, and it uses 17-20w idle instead of 10-15w idle. This is also with cstates 3,6,7 off, only 1E enabled.
Dont fully disable cstates, is a bad idea, 1E will give you most of power/heat gains, with pretty much no latency cost, I am able to run at 1.1v VCCIO and 1.15v VCCSA with "4" dimms, with 2 it should be extremely easy to reduce these. The bios had set them both to 1.25+ which was insane.
Bear in mind reports of these cpus been ovens, a lot of people aggressively overclock, 5ghz can require some quite high voltage but people will dial in as 5ghz is like a status symbol, instead I set the low voltage and then took the chip as far as it would go on that voltage, keeping it power and heat efficient.