RE: NAV 2016 Sync with CRM: Is it Multi-Company
The NAV side of the integration is specific to that company. So the integration will not see records in the other NAV company. However, you could have 1 CRM syncing to multiple NAV companies. You'd likely have to do some customizing but this should work.
A few other side-comments...
Be sure that your NAV2016 is ready to handle the OAuth requirements of CRM authentication--unless your CRM is older/on-prem.
If you go with multiple NAV companies syncing to 1 CRM, you'll likely need to have each integration instance running with a different CRM User. If you were to upgrade to BC, the integration creates it's own CRM non-interactive User account which would likely cause problems with that approach--not unsolvable but adds further complexity.