Hello @Witzker,
I suggest switching DNS Authoritative Name Servers Provider to one that supports the DNS-01 Challenge.
Note name servers provided typically does not have to be associated with the registrar nor the hosting provider, however they are often all the same for many domains & web servers.
This list is possibly getting stale but still useful