Я тоже столкнулся с этой проблемой в ларавел при изучении темы пагинации для сео. Сделал все практически так же, как и автор. Унаследовал LengthAwarePaginator, добавил условие $page>1. 

Единственное отличие - логику редиректов я реализовал не прямо в контроллере, а изолировал ее в Middleware:
%%(php)
public function handle($request, Closure $next)
    {
        // сразу определим есть ли пагинация на странице
        $page = $request->input('page') ?? false;

        // пагинации нет, отправляем запрос дальше
        if ($page === false) {
            return $next($request);
        }

        // здесь логика редиректов, если с номером страницы что-то не так
        .....

        return $next($request);
    }
}
%%
Дальше добавил этот посредник в группу web (т.е. для всех запросов).
Плюс в том, что это может быть применимо не только для одного контроллера. А в самом контроллере меньше кода.

Продолжая разбираться с темой пагинации, также решил передавать объект пагинатора в основной layout. И там реализовал для гугла rel='prev' и rel='next', а также rel='canonical' при необходимости, задействовав для этого методы LengthAwarePaginator (чтобы понимать на какой странице нахожусь). 

P/S Изучив кучу материала на эту тему, так до конца и не понял, как в итоге лучше всего поступать с метатегами для яндекса и гугла одновременно :( Авито делает canonical на первую страницу (причем с каким-то гео-параметром), хотя это вроде бы неправильно. Другие вообще закрывают ссылки на пагинацию, короче понимай как хочешь...