Yeah, those temps are way out of control. Package temp should never, ever, be 123 degrees C. I'm surprised it is even still working, IF the temps are accurate. Have you tried going into the BIOS to see what the CPU temp is being reported at? The unit should have throttled itself down long before those temps were reached I would think. If the fan is no longer running at high speed, it is either in need of replacement or it's not being told to run at high speed. As I mentioned before, you need to go into the BIOS and confirm the high CPU temps. You also need to, as mentioned before, go into the control panel power options, click on your current plan setting (Which is what, by the way?) and set the max CPU power setting to 99% and make sure the minimum cpu power setting is at 5%. Also, make sure the cooling fan policy is set to active and not passive. You can get there by clicking on change power settings for your current power plan and clicking on advanced power settings and then processor power management.
If everything is set as mentioned, I'd double check any possible BIOS settings related to the cooling fan. After that, it's probably a cleaning and a repaste of the cpu heatsink, and it might not be a bad idea to just change the fan if you've gone that far as the fan will be right there and likely have to be removed anyhow.