Zkuste toto:
$items = DB::table('items')
->join('catitem_item', 'catitem_item.item_id', '=', 'items.id')
->whereIn('catitem_item.catitem_id', $cats)
->groupBy('items.id')
->having(DB::raw('count(*)'), '=', count($cats))
->select('items.*')
->paginate(10);
S HAVING count(*) = 3
dotaz vrátí pouze položky, které mají všechny uvedené kategorie.