Should I trust VPN services that provide post-quantum encryption like NewHope for protection against future quantum computers? How can I tell if the connection between me and the VPN is using post-quantum encryption?
It seem a but premature to make a VPN decision based on post quantum protection considerations, at this time. I think much more important questions would be, company reputation and past actions. None/few of the major trusted VPN providers, I see have that as a feature and my speculation is that any services using the new crypto is likely still experimental, Microsoft just began looking into it about year and a half ago.
In summary, I would not use post-Quantum Crypto at the moment, and re-evaluate in the future.
To evaluate traffic from a vpn, you need to review your network traffic. I would start by looking into wire shark.