I repeated the complete process on a secondary device and faced the same error again. However, this time I was able to pinpoint the exact issue. My local Pi-Hole blocked two domains, that are addressed by the application during the activation of the notifications.
"firebaseinstallations.googleapis.com" and "in.appcenter.ms" need to be accessible for the app during the activation, I've received notifications without any issues, while blocking the domains on a DNS level, after the option has been activated in the app.