I had the same problem with Big Sur Beta 4 and Parallels 16. I tried all the suggestions except reinstalling MacOS and installing Parallels from the App Store. I had also deleted my Windows 10 VM to make room for Big Sur (was happy to recreate using Parallels). Used touch at terminal to create a dummy PVM file in case that helped but it didn't seem to.
What eventually worked for me was running this in terminal:
after a reboot and before starting Parallels Desktop.
This was after several attempts of sudo kextcache --clear-staging with reboots in between.
Parallels now happily running the Windows Installer.