iOS — Is there any way to send a gift to a user of another App Store?
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.