This is the demo code. It would help you much better. I tried covering both insert and update scenarios.
Inside app/Http/Providers/AppServiceProvider.php
Validator::extend('uniqueOfMultiple', function ($attribute, $value, $parameters, $validator)
    {
        $whereData = [
            [$attribute, $value]
        ];
        foreach ($parameters as $key => $parameter) {
            //At 0th index, we have table name
            if(!$key) continue;
            $arr = explode('-', $parameter);
            if($arr[0] == 'except') {
                $column = $arr[1];
                $data = $arr[2];
                $whereData[] = [$column, '<>', $data];
            } else {
                $column = $arr[0];
                $data = $arr[1];
                $whereData[] = [$column, $data];
            }
        }
        $count = DB::table($parameters[0])->where($whereData)->count();
        return $count === 0;
    });
Inside app/Http/Requests/Something/StoreSometing.php
/**
 * Get the validation rules that apply to the request.
 *
 * @return array
 */
public function rules()
{
    return [
        'name' => 'required|max:225|uniqueOfMultiple:menus,location_id-' . $this->get('location_id', 'NULL') . ',language_id-' . $this->get('language_id', 1),
        'location_id' => 'required|exists:menu_location,id',
        'order' => 'digits_between:0,10'
    ];
}
Inside app/Http/Requests/Something/UpdateSomething.php
/**
 * Get the validation rules that apply to the request.
 *
 * @return array
 */
public function rules()
{
    return [
        'name' => 'required|max:225|uniqueOfMultiple:menus,location_id-' . $this->get('location_id', 'NULL') . ',language_id-' . $this->get('language_id', 'NULL') . ',except-id-' . $this->route('id', 'NULL'),
        'location_id' => 'required|exists:menu_location,id',
        'order' => 'digits_between:0,10'
    ];
}
Inside resources/lang/en/validation.php
'unique_of_multiple' => 'The :attribute has already been taken under it\'s parent.',
Here in this code, the custom validation used is uniqueOfMultiple. The first argument passed is the table_name i.e menus and all other arguments are column_name and are comma-separated. The columns are used here, name (primary column), location_id, language_id and one except-for column for the update case, except-id. The value passed for all three is - separated.