I did clean the old paste from the top of the processor. "the pad from the bottom of the heatsink" I don't think so
This would cause a problem, firstly because the two mating surfaces would have a gap between them and secondly because TIM is intended to fill any imperfections in the mating surfaces so that when they are together the heat can be dissipated (gotten rid of) efficiently, the HS fan is designed to draw the heat upwards through the HS and away from the processor but if you have a gap between the HS and the top of the processor hot air will be drawn into that gap and over the top of the processor which may be the cause of your overheating/shutdowns.
I guess I have to lift off the processor and clean under it.
This is not necessary, you could remove and reseat the processor by all means but there should be nothing to clean from underneath it, I would leave the CPU (processor) alone this will prevent any possible damage being done to it such as bent pins or indeed debris/dust getting in.
As I said the PSU fan was blowing out hot air and it did seem a bit slow in turning
The PSU is meant to expel hot air but the fan should not be moving slowly this is allowing hot air to build up inside your case, which is then being circulated over other components and so getting hotter.
Also the heatsink screws on the MOBO is loose I can move it
Again not good, this may be due to the two mating surfaces not sitting flush allowing hot air to be drawn over the processor.
The old HS Fan was a 4 pinn the one I bought is a 3 pinn but it wtill works would that make a big differentce?
The 4th pin is used to control the fan speed but there are various ways a board can control the speed of the fan. The use of the 4th lead (PWM) is one, other's lower the voltage to lower the fan speed, when a molex and a single wire fan pin header is used on a fan, the fan pin header is normally for rpm monitoring and not for fan speed control.
You can use a 3pin fan on a 4pin fan header, you will notice that the "key" on the board fan header is fitted in such a way as to allow you to plug in a 3pin without any issue.
Things that we need to be certain are done and done correctly in no particular order as they all need to be done are;
1: Make sure the HS and CPU mating surfaces are cleaned off correctly.
2: Apply only the correct amount of fresh TIM to the top of the CPU.
3: Fit the HS correctly and securely.
4: Fit the HS fan correctly (make sure the fan is drawing the hot air upwards).
5: Make sure the CPU fan is working correctly, if the original 4 pin fan still works try that first.
6: Try a known good PSU or get yours tested by a Tech who has the correct equipment, I am particularly worried about you saying that the PSU fan was moving slowly, how slow is slow is hard to quantify when you are trying to explain it on a forum I know but the fan should spin faster and sound more powerful on boot up and then settle down to a steady/relatively fast speed and constant noise level, not noisy but not almost silent.