In testing found that the "paging" property is never returned. In the test we created a company (ID=7181446321) that had 600 contacts associated (verified from the HubSpot UI). The GET to crm/v4/objects/COMPANY/7181446321/associations/contact returned this raw response (499 other associations removed for brevity):
You can see there is no "paging" property in the response. Documenting here so this issue can be routed to the HubSpot development team for resolution.