Parallels Desktop 26 on MacOS Ventura very slow to start, wants to restart Mac on each launch

I just upgraded to Parallels Desktop 26 (26.1.1) on MacOS Ventura (13.7.8), and it looks like I shouldn't have.
Any time I start Parallels Desktop, it says "Starting..." for a very long time.
After a while, it will say that it needs to restart the Mac.
After a restart, it will display "Starting..." again for quite some time.
This makes using Parallels virtually impossible, I can't wait 30 minutes or more and restart my Mac every time I need to run a VM.
I already tried the workaround suggested in https://kb.parallels.com/en/129191 (which was supposed to be fixed in 18.1.0), no change.
What can I do?