How would an App Store possibly know? Surveillance often happens out of band, and under foreign jurisdiction. The apps themselves may not even know or may be prohibited from disclosing it.

That is something the apps and App stores can solve in collaboration. And if they are required to in order to make money, they very likely will.

this is literally impossible in any case that uses a server to process unencrypted data.

Or encrypted data where keys are shared or stolen.

If a government decides that it wants some data, they can just take it and silence whoever they want along the way. If someone is given a choice between prison or lying to an App Store, they will usually pick the latter. And if people don’t cooperate with you, you can just require them to employ agents of your government to do your work for you. Or nationalize the company entirely. Or require them to design their service in an exploitable way. Or exploit the underlying infrastructure they run on.

What if the phone/appstore is Chinese?

If they do not operate in the US, then US laws don't apply.

If the do operate in the US, they must comply with US laws.