This is usually due to the domain in question (zone) already being signed up on Cloudflare (active or pending).
What’s happening is that Cloudflare responds with the nameservers (NS) for the zone that is either currently active or first signed up. As DENIC is strict, when you try to set your assigned nameservers they believe the wrong NS are responding thus they prevent you from setting these nameservers. In reality all Cloudflare nameservers respond to all Cloudflare zones so if they would actually allow you to change nameservers then all would be fine.
Note: if you control the previous zone sign up, simply delete it and then let Cloudflare Support know that you have a strict registrar and need them to purge the previous zone. Otherwise you can wait (about two weeks) for the other zone to be purged automatically.
To check what Cloudflare NS are assigned for the domain in question (you can query any CF NS like Jake):
$ dig ns @jake.ns.Cloudflare.com example.com
;; ANSWER SECTION:
example.com. 86400 IN NS bill.ns.Cloudflare.com.
example.com. 86400 IN NS lily.ns.Cloudflare.com.
If the above check comes back with nameservers that aren’t assigned to your account you can be fairly confident that your zone has already been signed up (and it may be active or pending). This is not an issue if you could actually change your nameservers without the registrar complaining as eventually any other zones would be pushed aside as your domain activates.
If the above command comes back with your account’s assigned nameservers then you are all set and should be good to set your nameservers at your registrar.
There are a couple solutions here if your registrar puts you in this situation:
You can wait and if the other zone doesn’t activate (e.g. they don’t change NS to their assigned nameservers) then Cloudflare will eventually remove the zone in the way and start responding for your zone. This can take some time however (multiple weeks from when the zone in the way was signed up, not your zone).
You can contact Cloudflare Support and tell them you are using a registrar which is strict and therefore you need them to confirm you are indeed the zone owner (through a TXT record set at your authoritative DNS). Once Support verifies ownership they can change your zone to be the one Cloudflare responds to. If you don’t set the TXT record they provide, they won’t make that change so do make sure to set the TXT record appropriately.
Lastly, remember that there are millions of zones on Cloudflare and ultimately they respond DNS wise to whomever signs up the domain first (that is not the same as activation). As such strict registrars put their customers into a tricky situation as they think they are protecting you when in fact they are hampering your sign up process with Cloudflare.