[rest] What are best practices for REST nested resources?

What you have done is correct. In general there can be many URIs to the same resource - there are no rules that say you shouldn't do that.

And generally, you may need to access items directly or as a subset of something else - so your structure makes sense to me.

Just because employees are accessible under department:

company/{companyid}/department/{departmentid}/employees

Doesn't mean they can't be accessible under company too:

company/{companyid}/employees

Which would return employees for that company. It depends on what is needed by your consuming client - that is what you should be designing for.

But I would hope that all URLs handlers use the same backing code to satisfy the requests so that you aren't duplicating code.