You've replied to a discussion that's over 5 years old. We generally prefer members start a new topic than re-open an old discussion.
In this case, I'll reply to your question. I gather you used CCleaner's Registry cleaner; you seemed to imply that in your post. While I've used CCleaner for years, including its registry cleaner, and will continue to do so, other members of the forum are strongly opposed to use of ANY registry cleaner. Keep in mind CCleaner can be a useful tool without using its registry cleaner.
I suggest you reinstall Paint.NET on top of your current/old installation and then try uninstalling it via Windows standard removal tool (in Control Panel).
Other possible solutions could include restoring to a Restore Point that dates back to a time prior when the problem started, if you think you have such a Restore Point available.
