So I got a response from Google.
The problem was actually not about the App itself.
They do not like the screenshots in the Google Play Store listing, because they think I'm using unlicensed images. I will not get into a fight with them about what constitutes fair use and will create new screenshots with some web comics I also used for the IPad listing.
I would expect that the free Android version is back in the market within the next few days.