Я сделал вот, что (и вроде работает):
SELECT ... FROM ... ORDER BY ... LIMIT $Mes_count, $Mes_limit,
где $Mes_count - начальная старока (изменяется простым умножением на переменную $page(по-умолчанию равной 0, и изменяющейся на 1);
$Mes_limit - cоответственно количество выводимых строк.
Это информация для тех кто интересуется или ищет (будет искать) ответ на такой же вопрос.
Но хотел бы уточнить - Где надо использовать СOUNT(*)?