You can NOT run your CPU without a heatsink. You MUST use a heatsink with any processor. When you ran the computer without the heatsink, you risked damaging the CPU.
The part that melted was just the heat-paste/wax, it was supposed to melt. I hope you left it on there. If the heatsink still has some paste left, re-attach it to your motherboard and leave it there. Otherwise, buy more paste before reattaching and turning the computer back on.
And, yes, you should probably use both 2x2 plugs, but that did not cause your over-heating problems.