If I turn off the VPN, then Safari bookmarks syncs to iCloud just fine. However not all iCloud services are affected by the VPN, for example iCloud Photos sync works if VPN is on. Also Safari tabs seems to work. I’m using WiFi as my connection method and F-Secure Freedome as my VPN.
This message appears to MacOS Logs when this problem happens:
501:com.apple.SafariBookmarksSyncAgent.XPC.BookmarkSyncNetworkConnectivity:F46B15:[
{name: NetworkQualityPolicy, policyWeight: 8.400, response: {Decision: Must Not Proceed, Score: 0.00, Rationale: [{[wiredQuality]: Required:20.00, Observed:0.00},{[wifiQuality]: Required:50.00, Observed:0.00},{[networkPathAvailability]: Required:1.00, Observed:1.00},]}}
], FinalDecision: Must Not Proceed}
Have you found a solution? I have the same problem with the same console message. My bookmarks sync properly when I turn my VPN off. (Cloudflare WARP)
Interestingly, iCloud Safari history doesn’t seem to be affected. Only iCloud bookmarks.
I have the same problem using Cloudflare WARP too. However, it seems to work on iOS/iPadOS.
Update: For anyone googling this issue:
There is a ‘local proxy’ feature in the new WARP update. Using it solves the issue. The only downside is that some apps might not respect the proxy settings.
To enable it,
WARP Preferences > Advanced > Configure Proxy 
Enable proxy mode on this device
Now go to macOS System Preferences,
Network > Advanced > Proxies SOCKS Proxy
In the Socks Proxy Server box, type 127.0.0.1 in the next box, type 40000 Click OK, Click Apply. See Screenshots
Now 99% of apps should use the proxy including Safari. (Some apps like the Terminal and Adobe apps will not use the proxy)
You also might have to configure Chrome or Firefox to use the proxy in their preferences. I don’t use Chrome or Firefox, you are on your own on that one.
Thanks for this solution, do I need to set up a local proxy across all devices using Cloudflare WARP or just the affected device (my laptop)?
Enable proxy mode on this device