The "CRUD" (Create, Read, Update, and Delete) permissions at the profile level allow users to create, read, update, and delete records at all. Without those permissions, it doesn't matter what sharing says.
As an analogy, imagine a secure building and you have a security badge. Your badge will allow you to enter the building, and certain rooms inside the building.
In this analogy, the badge is a profile, the building is an object, and certain rooms are specific records. If your badge doesn't allow you in the building, it doesn't matter what rooms you have access to. Similarly, if you don't have access to an object permission, it doesn't matter what sharing says you can do with that record.
Make sure you give your users the C, R, and U permissions for the object. Sharing will prevent them from editing records they should not.
Best Answer
You simply have the permissions hierarchy inverted, which is easy to do given the complexity of Salesforce's security model.
The base of the pyramid is FLS and CRUD. Those permissions allow the user to interact with records of the object to which they have access. If a user has no Edit access in CRUD, they can't edit any records of the object.
The upper layer is ownership and sharing. If the OWD is Public Read Only, the user (who has Edit permission in CRUD) can edit only those records that they have Edit-level permission to, from the record-sharing layer. That means they own the record, they're above the owner in the role hierarchy, it's shared to them with edit rights, and so forth.
So: here, all you need to do is grant Edit permission - but not Modify All permission, which overrides the sharing layer and would allow the user to change all records regardless of sharing.