Ok, I am so far as to pinpoint the problem to DNSSD. Obviously, something is broken. Unfortunately, all I could find was the small bug report, that I shared above. Once the printer is installed, it is smooth sailing. I therefore assume, that the problem occurs only on a fresh installation, when the printer has to be discovered for the first time. So, the bug reports will follow in the months / years to come…
There is a SOLUTION anyhow! It is possible to connect the printer driverless via it’s ip (set a fixed IP in the router) manually:
Thank god (or better, the godlike @ namitutonka ) for this tutorial!