If anyone still has this issue, and cleaning the caches and reinstalling did not work for you, this worked for me:
1. Use Parallels toolbox or some other trusted application cleaner to uninstall Parallels and all related app directories and caches.
2.1 Check if you have any folders that have been configured to be used for virtual machines.
2.2 If so, if you happened to have them in iCloud, make sure they are downloaded/synced.
2.3. For example, I had a folder that I used to share files between my VMs and host machine, which was not locally downloaded.
2.4. (Optional) Not sure if needed but I also ensured all my VMs were locally downloaded and then moved them to a new directory.
2.5. (Optional) Not sure if needed but I made sure to stop/exit all VPN services.
2.6. (Optional) This by itself did not work for me but was likely required anyways (since root was not the owner) from an existing KB [1]:
"Wrong permissions to the necessary folder on the Mac side."
"Run: sudo chown -R root:wheel /Library/Preferences/Parallels"
3. Run the Parallels automatic installer.
4. Reboot.
5. (Optional) Again, stop/exit any VPN services that may have started on login.
6. Open Parallels desktop.
[1] https://kb.parallels.com/122953