El problema que veo es que primero obtienes
busqueda desde
$_POST y en la paginación, siendo enlaces, envías sólo el número de página y no incluyes lo que se va a buscar.
Te recomiendo que el formulario sea por método get y que también incluyas
busqueda en los enlaces de paginación:
<a href="<?php printf("%s?
busqueda=%s&pageNum_mostrar_datos=%d%s", $currentPage,
$colname_mostrar_datos, 0, $queryString_mostrar_datos); ?>"><img src="imagenes/First.gif" /></a>
Aunque habría que revisar como queda el HTML final, tengo mis dudas por como estás armando
$queryString_mostrar_datos, pero ya afinarás esos detalles.