Tested: the Perplexity app works fine for me over Windscribe VPN: both the VPN on my router and from the VPN app directly on the mobile device.
I’m not trying to downplay your problem, but it’s also not true that Cloudflare blocks all VPN connections.
But let’s call a spade a spade here: many VPN users do all sort of shady things behind those connections, leading to poor IP reputation for most VPN providers’ IP addresses and thus likely to trigger security challenges or even be blocked entirely.
Perhaps you can try another VPN, like the Windscribe I used.
What I said was people/users of public VPN services often do shady things behind them. And since the IP addresses are shared and not dedicated to the individual users, the result is collateral damage for all users.