Prvo pravilo: najveca greska je "SELECT * FROM ... " da bi dobio koliko ima recorda. Zamisli da ih ima milion? Za to imas "SELECT COUNT(*) FROM... "
Što se ostaloga tiče, to je obična matematika za osnovnu školu (i to dok još imaš učiteljicu

) i mogu samo da ti pomognem savetom, nadam se da Ilija nije u pravu da očekuješ da ti neko pošalje gotov script.
MAX = ceil ($count / $records_per_page); - to ti je ukupan broj strana
Dakle, kada si na strani X, i hoćeš recimo da prilkažeš 5 strana pre i 5 strana posle:
$pocetna = X-5
$poslednja = X+5
Zatim proveriš da li ti je početna < 1, ako jeste onda je 1
Pa proveris da li ti je poslednja > MAX, ako jeste onda je MAX
^ ovo je bas ono najosnovnije, ima tu jos nekih provera, jer to radi ako si na primer na strani 30 od 60 strana, ali ako si na strani 3, prikazace od 1 do 8 a treba od 1 do 10.... treba da radis i tu proveru. Isto vazi i kada je stran pri kraju.
Ono sto ti jos treba je nacin da napravis pravi url jer ako samo dodajes na string "&page={$page}" svaki klik ce dodati to na kraj a treba ti samo jednom.... dakle i na to moras da pazis.