CRM NAV connector - do we need a CRM license for the connector?

The answer is yes, but only to create the account, then the license can be removed. Check out this to get more details:

https://technet.microsoft.com/en-us/library/jj191623.aspx

1. Create a user account in the Office 365 admin center.
   Be sure to assign a CRM Online license to the account.
2. Go to CRM Online.
3. Go to Settings > Security.
4. Choose Users > Enabled Users, and then click or tap a user’s full name.
5. In the user form, scroll down to the Client Access License (CAL) Information section and select Non-interactive for Access Mode.
   You then need to remove the CRM Online license from the account.
6. Go to the Office 365 admin center.
7. Click Users > Active Users.
8. Choose the non-interactive user account and in the right-side menu under Product licenses, click Edit.
9. Turn off the CRM Online license and click Save.
10. Go back to CRM Online and confirm that the non-interactive user account Access Mode is still set for Non-interactive.