@Luch Filip's solution works well if you just want to rename the App package. In my case, I also want to rename the source package too, so as not to confuse things.
Only 2 steps are needed:
Click on your source folder e.g. com.company.example
> Shift + F6 (Refactor->Rename...) > Rename Package > enter your desired name.
Go to your AndroidManifest.xml, click on your package name > Shift + F6 (Refactor->Rename...) > enter same name as above.
Step 1 will automatically rename your R.java folder, and you can build straight away.