This is how I proceeded:

I have used a freeware tool called "a-pdf text extractor" from a-pdf.com. This allows text to be extracted with position.

Then I slurp in the resulting text file, remove duplicate entries and extract those lines that I'm interested in. Using a more advanced version of the code above I can put links on some 50% of the pages on the pdf file. In order to get close to 100% I had to patch 1 line of PDF::API2's source code.