I tried everything above to no avail. Got it working by additional steps. Listing all I did, maybe step 1 is not necessary.
Big Sur 11.3.1, Parallels 16.1.2 on a custom hackintosh build.
1. open mac System preferences - network. Select Parallels shared and press minus button to remove it. After it asks whether to reinstate network when it appears again, press yes. Then click APPLY. You must not forget to click apply.
2. open Terminal, sudo su [enter], type password, [enter]. You are now root.
3. list all running parallels services
bash-5.1# ps -ef|grep [P]arall
501 129 1 0 3:12PM ?? 0:00.95 /Applications/Parallels Desktop.app/Contents/MacOS/prl_client_app --start-services
0 568 129 0 3:14PM ?? 0:00.01 /Applications/Parallels Desktop.app/Contents/MacOS//Parallels Service start
0 570 568 0 3:14PM ?? 0:00.01 /bin/bash -s -- start /Applications/Parallels Desktop.app
0 578 570 0 3:14PM ?? 0:09.04 /Applications/Parallels Desktop.app/Contents/MacOS/Parallels Service.app/Contents/MacOS/prl_disp_service --pidfile /var/run/prl_disp_service.pid --launchd-mode
0 595 570 0 3:14PM ?? 0:00.54 /bin/bash /Applications/Parallels Desktop.app/Contents/MacOS/watchdog start 60 20 /Applications/Parallels Desktop.app/Contents/MacOS/prl_naptd start
0 618 595 0 3:14PM ?? 0:00.43 /Applications/Parallels Desktop.app/Contents/MacOS/prl_naptd start
As you see, there are still many running despite parallels is closed.
4. Kill parallels services. Use PIDs from the second column, and use them in reversed order (last to first).
kill -9 618 595 578 570 568 129
Now parallels is dead dead, murdered, nuked. We can edit the file.
5. Edit the /Library/Preferences/Parallels/network.desktop.xml
Add <UseKextless>0</UseKextless> anywhere between lines <ParallelsNetworkConfig schemaVersion="1.0" dyn_lists="VirtualNetworks 1"> and <VirtualNetworks id="0" dyn_lists="VirtualNetwork 6">
6. Start parallels services
/Applications/Parallels\ Desktop.app/Contents/MacOS/prl_client_app --start-services &
(press 2x enter after this command)
7. Start parallels app and the VM.