If it has to be distilled, then you'll need to acquire Acrobat (the paid version). That or ditch Quark and grab a copy of InDesign (good PDF export capability in CS and later versions).
You can try try print to PDF option first, then send it to the paper and see if it'll work. I've sent such PDFs to a variety of production houses on differing machines (4-color, single color, digital presses, copier-based, etc.) and haven't had an issue yet—then again that could be attributed to luck. Doesn't cost anything and the newspaper should be able to tell mighty quickly if the file is usable or not.