Without coding this is not possible.

Record Rules are based on the current user (res.user) and the department is stored in the employee (hr.employee). In the user there is not field which relates to the employee and therefore it is not possible to create a record rule for your requirement.

It would be possible if you add a function-field to the res.user object which returns the related employee.