Всъщност сте доста близки. Необходимият формат е:
[
98 => ['company_id' => 129],
99 => ['company_id' => 130],
100 => ['company_id' => 131]
]
Това трябва да генерира правилния масив:
$extra = array_map(function($companyId){
return ['company_id' => $companyId];
}, $allCompanyIds);
$data = array_combine($allPositionIds, $extra);
$user->positions()->sync($data);