Stock heatsinks come with a thermal pad. It would take hundres of degrees celcius to literally MELT a heatsink...it is after all a sturdy metal.
Those 64's have automatic thermal shutdowns so I doubt anything is fried.
The thing that'd be melted to the CPU would be the thermal pad that originally came on the stock heatsink.
Either get an aftermarket heatsink which they always come with thermal paste included, and apply that.
for instructions on how to apply the goop to your specific CPU. Even if you aren't using the arctic silver brand paste, it still gives you basic instructions for proper goopage.
You could simply remove your current stock heatsink, use something like a credit card and remove the thermal pad that was on there and reapply the heatsink with some thermal paste.
I say use a credit card because you don't want to scratch up your heatsink.