I figured it out by myself: https://stackoverflow.com/a/45881950/393157
I want to repeat, that this kind of problem is very annoying, time wasting and feels exceedingly unnecessary.
I found another root cause for this, and another solution:
Just create, then delete, a RDS in the target region!
AWS RDS simply refused to copy a snapshot, no matter what I did to key policies, UNTIL I created a small, automatic RDS. Now any key works "out-of-box", even new ones without any policy change!
Minimal KMS permissions to copy a database snapshotasked 5 years ago
KMS Customer Managed Key with cross-account service role permissionsAccepted Answerasked 2 years ago
RDS PostgreSQL snapshot and restore to a different accountAccepted Answerasked 2 years ago
Automate snapshot copy across regionasked 2 years ago
How to copy RDS database from Account A to Account Basked 6 months ago
Can an AWS RDS SQL Server Audit File be encypted with a kms key prior to upload to S3?asked 10 months ago
Enable RDS Encryption with minimal downtime after creationAccepted Answerasked 2 years ago
Correct permissions to Restore an Aurora Backup from AWS Backup with KMSasked 8 months ago
Add encryption to a multi-az cluster db snapshot?asked 3 months ago
Copying RDS Snapshot to another accountAccepted Answerasked 2 years ago