Is it compliant with Google policy to use push notification to one of my app to cross promote my other apps?
Of course not. It’s still kind of advertisement…
Obviously not allowed.
General rule of thumb when it comes to using notifications: if it’s not part of an integral feature of your app, don’t use them.
Well said Lockdown.
Couldn’t have put it better myself. 
Is that possible with Amazon App Store?
Amazon does not prohibit push ads as far as I’m aware, so by all means.