I just found out that you can't upload APK files with butler on Windows (see this topic) and that butler had turned my APKs into ZIPs. I wish I had realized this earlier and that people who downloaded the Android version would have mentioned that it didn't work.

I had uploaded the first version directly to itch.io and it showed up as an APK so I thought it would work like that with butler too – and apparently it should work like that. Yeah, obviously I should have paid more attention to what extension the uploaded file had but when you upload an APK, you kinda expect it to stay as an APK... sigh.

Anyway, I just reuploaded the APK files directly to itch.io and they should work now.