I didn't even realize they had a separate store. I guess I have to look into uploading there too.

APKs aren't their issue here, right? It's the idea that Google wants your keys to list on the Play Store. In theory you could not list on the Play Store and just list on Amazon, avoiding the requirement to hand over the keys.