Reboot fails after failed disk erase when restoring from Time Machine
It seems it was the SSD. (Or the SATA controller - I'm not quite sure yet.)

Removing the SSD from its plug caused the Mac to at least display a black and white folder icon with a "?" inside (like here: https://support.apple.com/HT204156) That gave me hope so I purchased a Transcend JetDrive 725 for Macbook Pro Retina Early 2013 and inserted it. Wohoo, Cmd-Alt-R started Internet Recovery and "D" started Apple Hardware Test!

AHT said everything is fine, except the SATA controller has a problem ("4HDD/11/4000000: SATA(0,0)") but it seems to work fine so far. I'm not sure I need to worry because this error can also be a false positive according to Apple: https://support.apple.com/HT203648

I'll torture the new SSD with Disk Utility and by replaying my Time Machine Backup and then we'll see.

Oh: and plugging the Apple SSD into the USB3 enclosure supplied by Transcend and attaching this to a PC froze the PC before even displaying the BIOS screen. Connecting it to a running system does not create a new mount point and results in lots of errors in the system log. So this seems to confirm my suspicion that it was the SSD.