This is one of those, "it depends" as to what the best solution would be.
If they're going to be doing the job repeatedly, then investment in PDF software, such as Acrobat Professional would be the best way to tackle this. There's free stuff out there that natively works with PDF's where you can edit inside the software, Foxit and Cute Pdf are two that come to mind, although, I can't vouch for how well they work.
That said, if you're comfortable with it, I've got Acrobat and Word installed on my machine and if you want to email me the document I'll do the conversion and email it back to you.
If that works, send me a PM and I'll give you my email addy.
I just looked at a document I converted and going from Acrobat to Word does cause some loss of formatting. The more complex the document structure the more formatting it will probably lose.