Ok to wrap this all up now :
Apparently it was my internet connection all along. Although I was able to log into my wifi when I first turned on the Deck, it seems to have had problems updating and therefore the update was aborted incorrectly, causing the Deck to seize up. After re-installing via the image and tutorial linked above, I was able to continue as far as logging into my mobile hotspot (phone) to download the update. That worked, installation as well. I have created a visible guest network that I can connect to without problems. No connection is possible to my invisible 5ghz and 2.4ghz networks.
Since I the first installation and the subsequent bios update were successful, the Deck runs stable.
Final thought :
Should you also experience similar problems when updating as I did - the Deck doesn't really tell you what the problem is (except for the 1 frame error message I showed above). Try the whole update at the first setup via a hotspot from your phone or a guest network of your router.
If you end up in a bootloop, check out the post above with the linked tutorial on how to reset the Deck and try again. Freezes can happen during reset as well as during setup (language / timezone / network). In that case shut down the Deck completely (hold the on/off switch for 10 seconds) and try again until it works - I had to try and repeat for like ~7 times until it updated without freezes.
The 6 hours I have spend troubleshooting would have preferred to play something, but at least it seems to work now.
If anyone has a tip regarding not being able to connect to invisible networks, please tell me. Actually, I don't want to run the guest network any longer than necessary.