It's weird how everyone focuses on that part of the CLOUD Act. The CLOUD Act actually did two things: (1) that, and (2) provided an expedited way for the US to enter into Mutual Legal Assistance Treaties (MLATs) with other countries.
It was the MLAT thing that the various civil liberties groups object to (I'll cover the problems with those down below). There was very little objection to the first part.
The first part was not controversial because pretty much every country has something equivalent (for reasons I'll cover below), as did the US except specifically in the case of data covered by the SCA due to poor drafting.
One of the big reasons for the SCA was created was the emerging "third party doctrine" meant that instead of having to get a warrant or subpoena against you to get your data they could simply subpoena it from any of your service providers that had it. The SCA made it so the third party doctrine subpoenas would not apply to stored communications.
There were still cases where the government would need to compel the service provider to turn over the data. They wanted something with the probable cause requirements of a warrant but the delivery method of a subpoena. (A subpoena asks someone who controls the data to turn a copy over. A warrant is for when the government wants to raid the data center and seize the data. Since that involves the government directly acting where the data is located it only applies to someplace where they have jurisdiction).
So they created a new thing, the SCA warrant. The called it a "warrant" because it had the probable cause requirements of a warrant, but neglected to add something saying that in other respects it functions like a subpoena. I'll call this a pseudo-warrant.
The SCA was not the first pseudo-warrant. That would be the warrants under the Wiretap Act of 1968. Territoriality questions did not arise under that because by its nature the data it sought copies of was always in the US.
With the SCA the data might not necessarily be in the US. Years later Microsoft argued that because it is a "warrant" it should have the territorial restrictions that normal warrants have. The CLOUD Act clarified that it was indeed supposed to be like a subpoena as far as territoriality goes.
There have been some more pseudo-warrants created since then, but their drafters learned from the SCA and made sure the original legislation was clear on just what they were.
The reason pretty much every country has something like that, going back well before online documents, is because not having such a thing leads to big problems. If anyone in the country could shield documents from subpoenas (or whatever the equivalent is called in that country) by merely storing them across a border every company with documents that it needs to keep but that might be incriminating later would get sent to a storage facility across a border as soon as they were no longer actively using them.
For example as soon as a car company in Detroit releases a new car all the documents where during development engineers brought up safety concerns which management decided to not address would be sent across the bridge to a storage facility in Canada.
With electronic documents it is even easier. You would not have to wait until you aren't actively using the documents to stick them outside the country. Just stick your file server across a border and make sure you only have copies in country when someone is actively reading or editing them.
And so pretty much everywhere subpoenas compel someone in the country who controls the documents to fetch them (or copies) and turn them over. The actual location of the documents is completely irrelevant.
The thing that was worrying about the CLOUD Act was the MLAT provisions. MLATs are treaties where the participating countries agree on law enforcement. They include things like sharing information and cooperating on investigations. Normally these are enacted just like any other treaty. The executive branch negotiates them and then the Senate votes on ratification.
The CLOUD Act adds an expedited process where the Attorney General and the Secretary of State can sign an MLAT. Congress is not involved. These agreements allow foreign law enforcement to make requests directly to US service providers instead of going through the diplomatic channels normal MLAT requests go through, and they allow them access to stored communications that the SCA would normally block.
There are some safeguards. The foreign government is not supposed to intentionally target US people who are in the US and are not not supposed to use the data they get to infringe freedom of expression. There's also a 180 day window before these executive MLATs take effect during which Congress can block them by passing a joint resolution to do so.
Civil rights groups and many others were not impressed with those safeguards.