I'm fine with banning all apps from countries that require their app-makers to share data with the government. If that requires an international treaty to codify when a company must share data (e.g. only with a criminal warrant), then great, let's do that.
China would refuse to sign that treaty? Even better.
No sense in giving the market to apps that are illegal in your country just because they operate on the internet.
For decades, the US has been a leader in global policy so there is no reason to think of them helplessly bowing to North Korea in the fu.
As for the validity of the complaint: that would be handled the same as for existing free trade treaties, i.e. slowly.
But other governments should ban such apps. The CLOUD Act drafts all American tech companies into the US intelligence gathering apparatus; all American companies providing services to foreigners are legally compelled to be spies. EU laws that require EU data to be stored in the EU? Nullified! The CLOUD Act undercuts any foreign data residency laws by requiring US companies to hand over even that data which is stored in other countries. All US tech companies are required by law to participate in espionage. The EU should respond by banning all American apps in the EU (but won't, for obvious realpolitik reasons.)
They're caught in a bramble bush and getting themselves unstuck is going to get them scratched up. But the longer they put off freeing themselves, the more the bramble grows around them. They should have done it years ago. They should do it now, before the "Trusted Computing" trap slams shut forever.
Finally, this hypothetical would say "a recipient country may ban the app." It wouldn't say "shall ban the app." So your country can just decide to keep using whatever they like.