Indexes and windowing functions
Your query for a specific department can make use of the index:
create index on employee_history (employee_id , last_update_ts desc);

The index without the desc indeed cannot be used.  I don't think there is a good reason for this, it is just some kind of oversight in the planner.  However, this index usage of the index that can be used is not going to be particularly fast anyway. It will have to read the entire index and table.  It will just avoid the sort of the entire table, not the reading of it.
This is a fundamental limitation of your questionable design.  Without some extra limitations (like employees can never move between departments) I don't see anything you can do about this in general.