To close this up:
I went to an Apple Store had the logic board replaced. Afterwards, I reinstalled from a backup and everything seemed fine...
But yesterday I noticed that I forgot to re-enable disk encryption (using File Vault). After enabling it and rebooting I got the exact same problem again. This time I also experienced the problem described here: Password incorrect after enabling FileVault
But unlike last time the problem disappeared (so far) after disabling encryption again.
If you wind up here looking for answers: Try disabling File Vault and check this for more details: MacBook startup problems - mouse and keyboard not working at login / stuck on apple logo