In the version of Eclipse that I use (Indigo service release 1), the Rename option is not suitable for the default package (unlike other packages), but if you select all classes, right-click and select Move to You could put them in a new package.
(As far as I can tell, the Rename option is for renaming classes without changing their package, but Move definitely works for moving between packages.)
Screenshots of the process:
initial situation

Select all classes and show the Refactor part of the context menu.

Select "Move", click "Create Package" and enter a name (mypackage in this case)

Final result

Alternatively, if you want to move them to an existing package, you can simply drag and drop the classes.
For those who offer Refactor -> Rename on the package, here is a screenshot showing what doesn't work on my machine:

Jon Skeet Apr 15 2018-12-12T00: 00Z
source share