So I could be off, as I'm no security expert, but with the research I conducted I found some references that shed some light on the above referenced link that scribu commented was malware.
Basically it's a php injection that exploits the view page php. The hackers are using Local File Inclusion vulnerabilities and
injection malicious code in proc/self/environ. It goes after the view page php and perhaps that's why Pagenavi is affected.
Now perhaps your issue Rafael is different since I haven't seen the code that is appended after your domain on the bottom navigation bar. But for me, I do believe that was the issue.
When this went down, I decided to move to a new host that was far superior in security (previously I was on shared hosting) along with installing the most popular WP security plugins (BulletProof Security, Secure WordPress, etc), downloaded a fresh install of WP and increased my password strength. Basically tried to make the best of the situation by upgrading the virtual walls around my domain. So far the issue has not returned. I 301'd all offending nav links that showed up in Google webmaster tools and will continue to monitor the situation.
So if your bottom nav links have something like this in them "option=com_product&controller=" then perhaps you have issues with malicious php injections.
Here's a few links I found, or you can type in 'php injection wordpress' into Google.
This explains how a forced php injection is done: