Quien dice link dice poner el valor del href en la barra de direcciones del navegador.
Lo que te quiero decir con esto es que nos digas como pruebas este script, ya que a no ser que reciba por GET el parametro llamado 'criterio', solo va a sacar todos los datos, que es lo que te hace ahora.
Si pones solo en la barra
http://localhost/paginacion.php
te va a dar como resultado todos los registros de la tabla.
Pero si pones
http://localhost/paginacion.php?criterio=pepe
entonces es cuando te tenia que hacer el WHERE.
Si quieres hacer la consulta con WHERE aunque no reciba 'criterio', debes quitar parte del codigo que crea el WHERE de dentro del if (isset($_GET['criterio']))
Saludos.