Asa cum zice puthre, lasi html-ul clasic, cum era inainte si il modifici cu javascript astfel incat sa ascunzi paginarea. E ideal atat dpdv SEO cat si pentru cei care nu au javascript.

Pe de alta parte, eu pun noindex pe paginarea categoriilor si ii dau voie sa indexeze doar prima pagina pentru ca sunt pagini fara continut unic si te poate afecta Panda.