Vale! Ya salen las dudas, entiendo el código y veo que debería haber envíado el mío, ya que no uso una condicional/bucle sin no una consulta sql.
Con esto le doy la paginación, en el que $tamPag; siempre es cinco (el valor que le he doy), $limitinfo son múltiplo de cinco empezando por 0 (0, 5, 10,...)
Código PHP:
<?
$sql="select * from palau ".$criterio." order by id desc limit ".$limitInf.",".$tamPag;
$res=mysql_query($sql);
while($registro=mysql_fetch_array($res))
{
?>
Añadir <input type="checkbox" name="nius_<? echo $registro["id"]; ?>">
<?php };?>
Pongo sólo este código a ver si voy bien.
Ahora viene la muy mala noticia, es que no entiendo bien las líneas importantes, no se de dónde sale el ($_POST['Enviar']) ni la función del interrogante, ... siento ser tan lerdo.