Did you try to do what it asked you to do? i.e. contact Cloudflare Support or try again later? (preferably both…)
P.S. How is it that you already knew which nameservers of Cloudflare to update in the registrar, before Cloudflare told you what they are, which happens after you add the domain, which you say you were unsuccessful to do?
Thanks for the additional information that was not there in your original question (otherwise I would have answered the below in my first comment)
Maybe you need it to be hosted elsewhere, with working DNS servers of another provider, for Cloudflare to be able to resolve it, and then you could add it. If you remove from Cloudflare, you really should go back to your original setup, not just delete the domain. In fact, you should do that before you delete from Cloudflare, because you want your website to continue to be operational…
Unlikely in this case. His nameservers are Cloudflare. And his nameservers won’t respond for his domain, because it was deleted from Cloudflare. They will start to respond when Cloudflare adds his domain to the service. But for that Cloudflare needs to be able to resolve his domain, which will not happen before they add it. So, chicken and egg.
That’s why I suggest to switch back to the original, pre-Cloudflare name servers. If there aren’t any and the registrar can’t provide, there are free DNS services at other places, e.g. https://dns.he.net.