hr.department model has a field called company_id
By default, this company_id field is filled by the current active company of the user on creation.
If this hr.department record, or a record of any other model which links to this hr.department record, is accessed by another user, odoo will look for access right if current user has access to the particular company_id

It seems you have multi-company enabled, so grant company access to the user by Settings/Users & Companies/Users, and select the user, and give access to company.