Laravel всё умеет. Нужно просто составить regexp, чтобы шли в учёт кириллические символы.
Например:
Route::get('test/{slug}', function($slug = null){
return 'Hello World, '.$slug;
})->where('slug', '[^0-9\p{Cyrillic}]+');
А так - копайте в сторону \p{...} модификаторов...