Respecto a tu duda acerca de la paginación, vuelve al echo como te dije, para ver que valor toma pag cuando te salen todos los resultados.

Y acerca de tu otra duda, puedes hacerlo con

<?php 
if(mysql_num_rows($query) != 0){
desplegarData();
}
else{
echo "No hay datos";
}
?>
 

Puede que sea el

while($row = mysql_fetch_array($query)) {

que hace que se repita todo otra vez?, hay otra forma de mostrar los resultados?

Hola, eso de que se repite la pagina ya lo arreglé, tenia que poner el echo paginar debajo del termino del while, pero sin embargo el buscador aparentemente no anda bien, me parece que voy a tener que hacer otro codigo, porque en la primer pantalla muestra los usuarios con filtro y en las siguientes todos los usuarios.
Por ejemplo si yo busco femenino, aparece en la primera bien, pero despues todos masculinos.
Entonces debe ser el codigo del buscador.
Veré que hago entonces.