Well this isn't going to go well for Google. At least I sure hope it doesn't. When corporations trump nation-states, we're all screwed.
So then I suppose Google should have just given in to the Chinese government's demands for censorship, or the US government's demands for access to private data?
I don't agree with either of those things, but there is a point at which globalisation comes into conflict with sovereign nations.
The status of a company is one that is granted to it by a sovereign country, and sovereign countries establish through their legal and government systems how companies can act within their borders.
Once you're there... yes, Google should comply to any legal request. And in fact, they do... as requests for data issued under legal order are in fact complied with.
Companies are not above the law (and laws tend to exist at country level or through treaty across many countries). And if the law of a country says pay, then Google need to pay unless another law can trump it and says not to pay.
There's no two ways about it, companies must comply with the laws of whatever land they operate in.