Hi @jaWa ,
Please check whether your library has unique permissions or not.
Click your library > Settings > Library settings > Permissions for this document library (if you can see "Delete unique permissions", it means this library has unique permission)
If your library has unique permissions, you need to grant user or group with "Contribute" or "Edit" permission again. And like you said, users with "Edit" permission they also should have the right to delete files to use "move to" option. Settings > Site permissions > Advanced permissions settings > Permission Levels > Click "edit" > select "delete item"
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.