Para renombrar el nombre del paquete, puedes realizarlo como indicas 

botón derecho en paquete > `Refactor` > `Rename`, en algunos casos aparecera la siguiente ventana:


[![introducir la descripción de la imagen aquí][1]][1]

indica la confirmación para refactorizar el paquete en esas incidencias.

Para finalizar revisa dentro de tus archivos `build.gradle` de la aplicación, la propiedad  `applicationId` que tienes que cambiar manualmente.




  [1]: https://i.sstatic.net/J2OeW.png