Antes de responder a pergunta em si, um detalhe importante que pode causar muita confusão nos seus testes: não se esqueça de definir o caminho base!
Isso pode ser feito no .htaccess, mas a forma mais simples é fazer pelo html mesmo:
<!-- inclua isso no "head" do html -->
<base href="http://a_url_do_seu_site.com/" />
Assim, principalmente quando se trabalha com muitas pastas e subpastas, arquivos com seções e subseções, não se perde o início absoluto da navegação para referência de todos os links.
No seu caso, se "categorias" for sempre a base, você poderia fazer isso:
<!-- inclua isso no "head" do html -->
<base href="http://www.meusite.com/categoria/" />
E todo o retorno das urls amigáveis começariam com "produto/página", ignorando o categorias, que seria sua "home", por assim dizer.
Voltando ao seu problema, esse tipo de situação é o que a gente chama de "múltiplas entradas", quando há mais de um arquivo .php para chamar, em vez de apenas um index.php. Neste caso, o .htaccess pode ser configurado de duas formas.
Primeira Opção
RewriteEngine On
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule ^(.*)$ index.php?p=$1
Aqui não muda nada em relação ao caso de entrada única, mas os arquivos existentes também são chamados pela query string "amigável". Para isso, basta convencionar que o primeiro parâmetro (no seu caso) é uma pasta, e o segundo é o nome do arquivo. Por exemplo:
www.meusite.com/categoria/produtos/2
extraindo a query srtring:
$qs = explode("/", ltrim($_GET['p'], "/"));
$caminho = $qs[0];
$arquivo = $qs[1].".php";
$parametro = $qs[2];
// e assim sucessivamente...
O mais importante nesse método é você entender que precisa elaborar uma forma de padronizar os endereços e a estrutura de pastas e arquivos do seu projeto. É mais fácil (e benéfico em diversos sentidos) você planejar bem o projeto, do que ficar queimando fósforo com o .htaccess.
Segunda Opção (não recomendo, mas existe)
RewriteEngine On
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule ^(.*)$ $1\.php
O que muda, é que agora você pode passar caminhos completos, e o último parâmetro (sem barra) será o nome do arquivo php. Acho que nem preciso dizer que não há vantagens nessa abordagem no seu caso, principalmente porque ela dificulta a passagem de query strings.
Para finalizar, eu vejo algo que poderia ser mudado no seu código da paginação, que está assim:
if(empty($_GET['page'])){
$page=1;
}
if($page >= '1'){
$page = $page;
} else {
$page= '1';
}
Quando seria mais interessante fazer isso:
$page = 1; // por padrão, page é sempre 1
$dir = "produtos"; // outro padrão, por exemplo
if (!empty($_GET['page'])) { // todo o resto só faz sentido se houver dados
$dados = explode("/", ltrim($_GET['pages'], "/"));
$dir = $dados[0];
$page = empty($dados[1]) ? 1 : $dados[1]; // só por garantia...
}