I have the same permission level. I named it ContributeNonDelete.
And it works as expected.
Be sure that following checkbox are checked in your permission level:
View Application Pages
Use Self-Service Site ...
You need to check all the content with unique permissions - thinking about it logically, the folder which you cannot rename might have unique permissions. So even though you have Full Control on the rest of the Site or Library, it is possible that the folder has unique permissions - you might only have Read permission.
Go to the Library Settings > ...
Try to check permissions by clicking on the "Check permissions" button on site permissions and list permissions settings.
It looks like members of the group also have membership in another groups with higher permission level.
I don't know if is it the best way, but I have created a Flow, with HTTP Trigger and input parameters:
siteurl, listName, itemId, and an array of user-permisison objects like: