Después de compilar el apk tienes que coger el META-INF y androidmanifest.xml de la apk original y copiarlos a la apk ya compilada.
Si ya has hecho eso lo que falta sería darle los permisos necesarios con algún explorador root.
Nota: los iconos que quieres cambiar deben ir a la misma resolución que las originales.
Suelen encontrarse en las carpetas drawables.
Pd: deduzco que ya sabes compilar y decompilar apk
Espero que te sirva y un saludo