Push notification cross-promotional advertising violates the following policy:
System Interference:
Apps and their ads must not display advertisements through system level notifications on the user’s device, unless the notifications derive from an integral feature provided by the installed app (e.g., an airline app that notifies users of special deals, or a game that notifies users of in-game promotions).
I think yes, I’ve seen this many times for the Talking Santa app which sends me a push notification about the Talking Tom app. The push opens the Talking Santa app but the first I see is a full screen interstitial advertising the Talking Tom app. And of course the click on the interstitial leads to Play Market. So I guess it’s safe, unless only the big guys are allowed to do it))