I have finally found the reason why this fails: Most likely this was because of dead-locks between multiple certificate update challenges which seemed to be duplicated. Removing only the challenges didn't work. But after removing the failing certificates and then all waiting challenges and reapplying the certification yaml, the challenges worked without a problem.

Additional stuff I made, which probably was unrequired but just to be sure: Created a new cloudflare token with the rights zone:zone:read and zone:dns:edit on all zones (https://cert-manager.io/docs/configuration/acme/dns01/cloudflare/). Removed the cloudflare-secret-token manually and updated the yaml file (or add the cloudlfare-secret-token with the updated token manually). Removed all pods; Removed all orders; Removed all challenges; Removed all acme challenges in cloudflare. Reapplied everything.