The Content Staging documentation should be more specific on the fact that both servers should have the language of the object content being published.

More specifically, the siteaccess on which the REST API endpoint is used should have all languages from the source server configured in the site.ini's SiteLanguageList[]