That's not how cookies work, cookies are stored on, and controlled by, your client. Unless your client is sharing the cookie information across devices, google wouldn't be able to track you across devices using cookies.

Sorry, I didn't mean to imply the same cookie is shared between clients. Google place cookies when you log in, and they know all the cookies associated with your account. You could always do searches when you're logged out, across all your devices, which would prevent them from tracking you cross-device. It's pretty rare for people to not be logged into a Google service though, especially on mobile.

Routing all of your searches to one machine allows google to build a richer search profile against you, rather than one scattered across multiple different IPs, device fingerprints, etc.

At the end of the day, your VPS is still having a search profile build against it, in a similar manner to just using your personal device.

You can get a bunch of people to use it though (friends and family). I also doubt they build profiles just based on IP, since it's not uncommon to share IPs given the IPv4 shortage. There's also CGNAT where hundreds of thousands of people share a sml number of public IPs.