That's true, but the $5 VPS should have a public IP, either v4 or v6. Other devices can route their traffic through it, and then every device can reach other devices, regardless of NAT.
On some OSes you could probably also use some additional 4->6 tunnel, but that probably doesn't work stacked under Wireguard on iOS and Android.