What they seem to be doing is just presenting a CAPTCHA to anything at all unusual. Which is actually kind of strange, given the vast amount of raw data available to them. They should be able to learn real indicators.
I'm actually not even sure Cloudflare is primarily responsible for most of this... exactly. The problem is more likely that Cloudflare gives its users a lot of knobs to twiddle, and most of the users are probably not up to twiddling them correctly. That could be the main source of these problems.
And there are so many possible combinations that it would be hard for Cloudflare to really test them, or even think about how all the knobs might interact.
Taking away knobs would be a good start, but there may be reasons they don't think they can do that. Probably reasons that are more about their customers' perceptions than about their customer's real needs.
Come to think of it, isn't one of those knobs the ability to turn off PrivacyPass? I don't have access to a Cloudflare account at the moment, but I seem to remember that it was.