Поиск общего значения Laravel

Если не хотите сильно нагружать бд, то можете попробовать сделать так. Получаем коллекцию городов, и сразу подключаем к ним регионы (внутри используется load, то есть всё в едином запросе к бд). Далее работаем только с коллекцией. Получаем регион для поиска и проверяем есть ли он в коллекции второго города! (Ну раз у Вас есть такая таблица которую Вы предоставили, то связь многие ко многим надеюсь у Вас настроена!) Код похож на Ваш, но с использование коллекций, а не запросов к базе данных.

$cities= Cities::find([$first_city, $second_city])->fresh('regions');
foreach ($cities[0]->regions as $key => $value) {
    if (count($cities[1]->regions ->whereIn('id', $value->id))) {
        return true;
    }
}
return false;

Второй пример использование связующей таблицы как исходную. Работа то же через коллекцию:

$table= DB::table('city_region')
        ->select()
        ->whereIn('city_id', [$first_city, $second_city])
        ->get()
        ->groupBy('city_id');
foreach ($table[$first_city] as $key => $value) {
    if (count($table[$second_city]->whereIn('region_id', $value->region_id))) return true;
}
return false;