Well, I finally was able to register the domain after I manually created a zone for it (via "Cloud DNS" / "Zones") and then choosing the zone in the registration process (step 2 "DNS configuration"). Earlier I was trying the option "Setup a new zone" in the registration process, but that would still produce the mentioned error (
"The attempted action failed. Please try again.").
Very misleading and confusing.