I’ve had very good luck with pdfescape . com. However, if you continue to run into the issue where it’s not seeing text, then I’m going to guess that what you have is essentially an image saved as a PDF. IME, you just can’t win trying to edit that. Even ‘erasing’ and typing over it is just never going to look correct. The chances of getting the same font in the same size with the same spacing are so slim that it’s always going to look like a hack job.
I’d first start by asking the boss if there’s another format/file available of the menu to see if you can get one that’s easier to work with. There’s a very good chance (for example) this is just the one that was sent to the printer and there’s text file as well. My logo is save in quite a few formats, often times people need a different one than the one I gave them.
After that, if it’s not a huge menu, it might just be faster to retype it and save it however you want so that it’s easiest for you to work with and edit going forward. OOWriter/Word is nice, but Photoshop/Gimp is super helpful for rearranging things and getting spacing just right.
The last thing, as I think you figured out is just to open it in a free pdf editor or convert it to a jpeg and, basically, draw over it. But either save that for last or find out how much time your boss wants you to spend on the project. I mean, if it’s like ‘you’re only changing 4.99 to 7.99, this shouldn’t take more then 2 minutes’, yeah, that’s the way to go, but if it’s retyping a few lines and the entire menu is just two sides of a page, it’s probably better to redo the whole thing and future proof it (after making sure there isn’t an editable format available first).
Oddly enough, I find Inkscape works really well for a PDF editor*. It converts it to SVG, and then it’s generally easy to pull apart the parts I want to fix. Even if the text isn’t text, you might be able to take out the part you don’t want and type in the new part. You can then save both the SVG, for later editing, and as a PDF.
Of course, that won’t help if it’s just an image file put in a PDF wrapper.
*When I need something besides the basics. If I’m just typing out text on top of a form or adding chords to sheet music, I use the types of software you already mentioned.
Dang, I was ready to be the first to post the actual best answer for free, pro level, yet easy editting of a .PDF of something like a menu, presumably destined for print. But, yup, Inkscape is your best answer.
P.S. Use the Poppler import option with as “fine” a quality as you think your computer can handle.