A big fat tip soldering iron, commonly called a hammerhead or chisel tip, will help a lot in these cases, because the FET pins (except the gate pin) are on huge traces that act as heatsinks and make it very hard to desolder or solder with a small tip iron.
It doesn't have to be a huge wattage iron, but that can help too--I use an 80w Weller with a chisel tip about the thickness of my pinky, for stuff like this, and heavy gauge wires, and it just works quick and easy like the smaller tips do on regular components and traces.
FWIW, you probably can't properly solder the FET legs to the existing leads sticking out of the board, because you first have to cut the legs off the new ones to the same length as the leads sticking out, whcih leaves very little space between the new ones and the board, to be able to reach with the iron tip.
(if you don't have them the same length, they won't be able to bolt to the heatsink or spreader bar, cuz the mounting tab hole will be at the wrong height. Also, another possible problem is if the legs arent' shaped to overlap the existing legs in the right way, the new FETs wont' be vertically parallel to the heatsink once mounted, and will not be able to shed their heat correctly)
The iron tip itself may not be able to heat them quickly enough to do the soldering for the same reason you can't heat the existing leads up enough to get them off, and if you heat them a long time you can damage the new FETs.
I use a solder sucker on some things, but solder wick works better for cleaning up holes after removing components. Sometimes to get the solder out with a sucker, you have ot first *add* solder to fill the hole completely to make the sucker work. Don't have to do that with wick.