I just had a hard time trying to figure out why, after uninstalling pasteformat, I kept getting error messages "Failed clean-up on paste, please contact your site administrator" when pasting text. Turns ouf if you don't disable the pasteformat Ckeditor plugin before disabling/uninstalling paste format you always get those error messages when pasting into text formats that previously had pasteformat enabled.
I don't know if that's easily doable but it would definitely be better if the uninstall routine could just disable the Ckeditor for any textformat where it was enabled.
The solution if you're stuck with this error: just re-install pasteformat and disable the Ckedtior pasteformat plugin. Then you can safely uninstall the pasteformat module.