É possível fazer algumas alterações no APK, mas isso depende de como ele foi gerado e assinado. O formato APK nada mais é do que um arquivo ZIP, quando visto de forma simplória.
Você poderia, em alguns casos, alterar os ícones manualmente usando um aplicativo como o 7-Zip ou WinRAR. Entretanto, acredito que a forma mais simples de fazê-lo seria usando o APK Icon Editor.
Basta carregar a APK no aplicativo e no menu Ícone utilizar as opções de substituição. O programa possui dois modos de operação, o ZIP e o APK Tool.
O primeiro faz uma substituição simples dos arquivos de ícone.
O segundo oferece recursos mais avançados, em maioria ligados à engenharia reversa. Você pode seleciona-los nas configurações do programa.
Outra opção é utilizar o programa APK Manager. É possível encontrar tutoriais com detalhes deste procedimento.
Após qualquer alteração, é necessário assinar de novo o pacote APK com uma chave válida de desenvolvedor (hoje custa 25 dólares, e a ferramenta é gratuita.
Aqui mais detalhes sobre como descompilar um APK e efetuar alterações.
Artigos relacionados:
Como cadastrar/vincular uma conta do Google em seu Android
Erro rh01/ rpc:s-5:aec-0 da Google Play Store. Como resolver?
Como solucionar o erro 923 da Google Play
Como solucionar o erro 921 da Google Play
Error 101 da Google Play Store
Como descompilar (decompile) e modificar um APK para Android
Como alterar o nome de uma coluna no Postgresql
Como resolver o erro “COM.ANDROID.SYSTEMUI PAROU” do Android
Como mandar comandos para seu Android pelo buscador do Google