I had a similar issue with MBP and Catalina lately. First I noticed I could not use my valid credentials to log in to App Store and Music. Someone said log out of iCloud and back again. Well, then I could not sign in to iCloud anymore. Error message varied from app to app, but in System Preferences it would say "Verification Failed: There was an error connecting to the Apple ID server".
Other Macs, iOS devices, and Apple ID and iCloud web sites worked fine. So there was something with this particular Mac.
After hours of trying safe boots, different networks, I deleted the remaining account (MS Exchange), and also could not reconnect to that. That motivated me to try deleting the ~/Library/Accounts directory (https://www.sunzala.com/fixed-apple-id-an-unknown-error-occurred/). Afterwards, I could log in to both iCloud and Exchange accounts.
Of course not without trouble; all my local mailboxes disappeared in Mail, and I had to re-import them from a folder found in ~/Library/Mail directory. It's surprising as local mailboxes should not be connected to any Internet account anymore.
Probably reinstalling and restoring data from backup would do the same thing, but more slowly...
