Rest – Bulk update: return all results or only failures

I think you have complexity because you are starting with over-complication:

Paths would be something as:

companies/1/departments/1/employees/1/courses/1
companies/1/offices/1/employees/1/courses/1

Instead I would introduce simpler URL scheme like this:

GET companies/
    Returns a list of companies, for each company 
    return short essential info (ID, name, maybe industry)

GET companies/1
    Returns single company info like this:

    {
        "name":"Acme",
        "description":"Some text here"
        "industry":"Manufacturing"
        departments: {
            "href":"/companies/1/departments"
            "count": 5
        }
        offices: {
            "href":"/companies/1/offices"
            "count": 3
        }
    }

    We don't expand the data for internal sub-resources, 
    just return the count, so client knows that some data is present.
    In some cases count may be not needed too.

GET companies/1/departments
    Returns company departments, again short info for each department

GET departments/
    Here you need to decide if it makes sense to expose 
    a list of departments or not. 
    If not - leave only companies/X/departments method.

    Note, that you can also use query string to make this 
    method "searchable", like:
        /departments?company=1 - list of all departments for company 1
        /departments?type=support - all 'support' departments for all companies

GET departments/1
    Returns department 1 data

This way it answers most of your questions - you "cut" the hierarchy right away and you don't bind your URL scheme to the internal data structure. For example, if we know employee ID, would you expect to query it like employees/:ID or like companies/:X/departments/:Y/employees/:ID?

Regarding PUT vs POST requests, from your question it is clear that you feel the partial updates will be more efficient for your data. So I would just use POSTs.

In practice, you actually want to cache data reads (GET requests) and it is less important for data updates. And update are often can't be cached regardless of what type of request you do (like if server automatically sets the update time - it will be different for every request).

Update: regarding the right "thinking process" - since it is based on HTTP, we can apply the regular way of thinking when designing the web-site structure. In this case on the top we can have a list of companies and show a short description for each with a link to the "view company" page, where we show company details and links to offices / departments and so on.

I would generally advise against having microservices do synchronous communication with each other, the big issue is coupling, it means the services are now coupled to each other, if one of them fails the second is now fully or partially disfunctional.

I would make a clear distinction between state changing operations and read operations (CQS Command Query Separation). For state changing operations i would use some kind of messaging infrastructure and go for fire and forget. For queries you would use Synchronous request response communication and could use an http API or just go directly to your data store.

If you are using messaging then you can also look at publish subscribe for raising events between services.

Another point to consider is (transactional) data sharing (as opposed to read only views) if you expose your internal state the reader might get the wrong state of your data, or the wrong version, and also will potentially lock your data?

Last but not least, try to do everything you can to keep your services autonomous (at least at the logical level).

Hope this makes sense.