Is it possible to rename a category on Wikimedia Commons (or another Wikimedia-based wiki) so that all of the pages in that category are moved to the renamed category instead of being left in the old category?
It's not directly possible to do that. But some wikis do have bots that can assist you with moving the items from the old category to the new one.
For Commons-specific information, including how to request renaming both to run, see Commons:Rename a category. I expect other large wikis will have similar pages.