I think this is less of an issue than people actually think - if it gets to the point where this becomes a real problem, individual EU countries can force the datacenter owners like Google/MS to change ownership structure for these datacenters to EU-based subsidiaries or completely new companies if they want to continue to operate.
This doesn't matter as far as the concerns about US warrantless surveillance laws go because those laws also apply to subsidiaries of US companies. IIRC Microsoft tried to argue that its EU subsidiary could not comply with US requests and lost.
Usually everything is through subsidiaries. For tax and profit allocation purposes the way it works is that you set up subsidiaries in tax-friendly jurisdictions and then channel the profits to them through contracts between subsidiaries.
The general point is what does "moving away from US cloud services" mean, then?
Does it mean not using infrastructure actually located in the US? Or does it mean effectively boycotting US-owned companies that may be fully located, including infrastructure, in Europe?
