The Problem was that the installation of GrapheneOS (and later even Stock Android) couldn't continue after the phone reached the "fastbootd"-menu. At this point, the PC lost the connection to the phone and could only find it again after the user manually rebooted the phone from the fastbootd-menu, which crashed the installation process.
It happend on different OS and different Browsers, Web Installer and Command line. Drivers were up to date.
The Solution was trying different cables (another user had this problem even with the cable that came with the Pixel) and USB-Ports