Not all menus are the same (or in the same place) thus it might not be looking in the "right" place.
Firstly, have you done a search of the repos using Synaptic to see whether it's available there? Do a Reload before searching.
You don't say which version of PCLinuxOS you are using - if it's KDE first make sure the Panel Widgets are unlocked.
Now right click on the Menu and choose Edit Applications.
Choose a place where you want the entry to be and then select New Item - give it a name and then drill down to where your application has been installed etc and then do a Save.
On a kind side note; for keeping your system in good shape it's much better not to install apps from outside the repos but to do a New Package Request where it can be looked at by the devs and if/when they have time will package it correctly for you. This requires you to have 10 or more posts