It's the bloody permissions again.
"Once downloaded, the malware asks for permission to access the internet and send and receive SMS messages."
Right this is a wallpaper app.
Google could easily go.
Dear developer. Justify this.
They come back with valid reason or disappear of the face of the Earth.
Then even with a valid reason, the OS goes, this app is trying to connect to a premium rate SMS / Phone number.
Block until allowed.
Ask user with a bloody great warning. This App is trying to connect to a service with high call charges. Do you accept the risks.
It's not that hard.
I'd go further than that.
All Apps should have "Deny ALL" until they can justify each and every access control they ask for.