Burning the bootloader from the command prompt worked after some fiddling and reading this:
https://forum.sparkfun.com/viewtopic.php?t=44209
However, I have not had any luck with bossac.exe so far. It stalls immediately after printing "Set binary mode" and I have to abort the process by pressing Ctrl+C. I have even tried the GUI version of Bossa but it stalls as soon as I select the relevant USB port 
One important detail I forgot to mention is that my board is an M0 with an Arduino Zero bootloader and not a true Arduino Zero with the EDBG.
The work continues.