Постраничная навигация должна быть не по номерам страниц, а номерам первых комментариев на очередной странице, т.е. в идентификаторе в url должен быть именно этот идентификатор а не номер страницы. При получении несуществующего 'первого' комментария, делать поиск по ближайшего наибольшего id (select ... where id > @current_page_id limit 1), то потребует инкрементального id (а так все и делают) это значит и сортировку комментариев на странице делать можно по нему, и вообще выборку.
Недостатки - сложно получить N-тую страницу, так как придется перебирать всю базу, но обычно никто не заморачивается с этим и обходятся первые M страниц, затем многоточие, затем ссылка на последнюю и количество страниц считать от общего количества комментариев.