It sounds like one of two things are happening:
1.)The heatsink isn't installed correctly. Make sure that the heatsink fan is plugged in and that the heatsink itself is secured to the motherboard or retention bracket.
2.)You have way too much thermal paste being used. A paper-thin layer is all that you want. Too much thermal paste will act as an insulator for the heat, defeating the purpose of thermal paste. Also, if the heatsink came with a thermal pad, you should not use thermal paste with it. Do note that the thermal pads are good for one application only. Before reapplying any thermal paste, clean off the old stuff with isopropyl alcohol first, then apply a paper-thin layer.
While you can use a 20-pin power supply with a 24-pin motherboard, it's not recommended. The extra 4-pins provide additiona 12V power to the system. And, no, a 20- to 24-pin adapter is not the same thing as a native 24-pin power supply.
Wattage doesn't mean anything. Amperage does. Wattage doesn't reflect the total amps in the right places. The sticker on the power supply should state how many amps there are on each rail (12V, 5V, 3.3V). If your power supply doesn't have at least 22A on the 12V rail, it's highly advised that you replace it with a better unit.
Still, what it looks like to me is that your cooling is the problem, and the motherboard is taking action to prevent damage to the CPU.