I am also getting this problem or at least something very similar, but I can be a little more specific:
I had Paint.Net classic installed then almost as soon as it was released I purchased and installed the app version from the store and began using it rather than classic (classic was still installed).
I have Controlled folder access turned on in Win 10 (Defender).
Today I cannot save to my 'My Documents' folder (or any other protected folder).
This is fairly new behaviour because I used to be able to do this (I say 'fairly new' because I haven't used Paint.NET for a few weeks).
I have now uninstalled the classic version, uninstalled the app and then reinstalled just the app but still have the same issue.
I don't know if it is connected but I have Windows set to install apps to D: but when reinstalling Paint.NET it wouldn't allow me to put it there (no reason given, just that the D: drive did not appear as an option). I installed to C: and then moved it using Apps and Features to D: where it now runs perfectly well from (Apart form the saving!).
Here is the error from Paint.NET when I try to save an existing file back to where it came from
And here are the details:
System.IO.FileNotFoundException: Could not find file 'D:\Users\XXXX\Pictures\XXXX\xxxx.jpg.0.pdnSave'.
File name: 'D:\Users\XXXX\Pictures\XXXX\xxxx.jpg.0.pdnSave'
at System.IO.__Error.WinIOError(Int32 errorCode, String maybeFullPath)
at System.IO.FileStream.Init(String path, FileMode mode, FileAccess access, Int32 rights, Boolean useRights, FileShare share, Int32 bufferSize, FileOptions options, SECURITY_ATTRIBUTES secAttrs, String msgPath, Boolean bFromProxy, Boolean useLongPath, Boolean checkHost)
at System.IO.FileStream..ctor(String path, FileMode mode, FileAccess access, FileShare share, Int32 bufferSize, FileOptions options)
at PaintDotNet.IO.SaveTransaction..ctor(String path, FileMode mode, FileAccess access, FileShare share, FileOptions options) in D:\src\pdn\src\PaintDotNet\IO\SaveTransaction.cs:line 265
at PaintDotNet.Controls.DocumentWorkspace.DoSave(Boolean tryToFlatten) in D:\src\pdn\src\PaintDotNet\Controls\DocumentWorkspace.cs:line 2915
Here is the error I get when I do a Save As on a new file, which I guess is triggered because Win10 won't allow write access to the folder.
In both cases I naturally get the Win10 notification that Controlled Folder access is blocked.
I hope this is useful and that you might be able to help me.