I suspect your fan is worn badly and close to failure. Here's what I suspect from your description.
When you first turn on, the fans (including the CPU cooler) are sent full voltage to be sure they start up. After a few seconds the system completes most of the POST self-test process and finally gets a temperature reading from inside the CPU chip, then adjusts its CPU cooling fan to match the relatively low temperature in there (because it has not run for very long). When the CPU fan gets this signal to run much slower it does that. BUT the fan's bearings may be so worn that it simply stalls at that "slow-run" setting. Then the CPU chip has NO cooling and heats up pretty quickly. At that point the mobo would try to speed up the fan, but it is stalled and needs a "high speed" signal to start up. Before it ever gets that, the CPU internal temperature goes so high the system shuts itself down to prevent damage to the CPU.
How could you test for that? The simplest test is with you finger. Shut down the system completely and open the case. With your finger, gently spin the CPU cooler fan. and let it go. If it feels stiff to spin it, or if it slows down very rapidly, the fan bearings are just about worn out and the fan should be replaced. If the fan keeps spinning and slows down slowly, it is probably OK.
If the fan is OK by this test, you might want to look closely at the way the CPU_FAN header's parameters are set in BIOS Setup. It is possible that it is set to allow a minimum speed that is too slow and you could change that.
If the fan test suggests it needs replacement, you MAY not need to replace the entire CPU cooler system, depending on its design. On many systems you can remove a few screws that fasten the fan to the heatsink without ever removing the heatsink from the CPU chip. Then you can buy a new fan of the same characteristics and just mount that in place of the old one. You might need some hints on what are "the same characteristics" if you go this route, so post back here if you need advice on that.