Two things to check, first the speed of your CPU cooler's fan, and the CPU temperature. Both of those things could cause this error.
The BIOS of most mother boards check the speed of the CPU fan, and if it is below whatever is considered to slow, that kind of message will be displayed. It is not enough to see that the fan is spinning, it may be going to slow.
Or, if the CPU temperature is to high, it is assumed your CPU cooler's fan is not working correctly, and that message is displayed.
Did your CPU cooler get moved or is not connected to the CPU correctly? That should be checked too.
Have you tried clearing the BIOS/CMOS, and then resetting any settings you use, in case there was a corruption in the BIOS.
Besides changing the CPU cooler's fan, none of the things you listed will do anything to stop that error. That message is not coming from Windows, and your power options are also unrelated to that error.
What are you using to check the CPU fan's speed and CPU temperature, since you are not using AXTU? What is your CPU fan speed usually, and what is the CPU temperature? You can see both of those things in the BIOS.