iOS — Is there any way to send a gift to a user of another App Store? The recipient of your gift must have an Apple ID in your country or
region. For example, if you're in the United States, you can't send a
gift to a friend who lives in Australia.

I'd like to send an app gift (a game), but I'm in Germany an the recipient is in Russia. Is there a way to do so?
There is no way around what you've already found.  Different countries have different rules so Apple enforces the rule when gifting apps.
You can send an Apple Gift Card to the recipient to have them buy the game.