Mh... I beg to disagree:
- Creating outlines is usually a bad idea, specially if you have tiny text and/or a big quantity of it. Embed fonts.
- 300 ppi for a newspaper sounds like overkill. 100-150 ppi is usually more than enough.
- CMYK... which one? A bad election will end in a PDF with way too much ink.
If you need to shoot a blind shot because of having no data, a PDF/X-1a:2003 with a standard profile like IFRA's ISOnewspaper26v4 (as described in http://www.medibelplus.be/pdf/newspaper/Photoshop_INP26v4_en.pdf) should be in the safe side. And it's dead easy to do.
A good resorce on choosing the right ICC profile to make a print-ready PDF is http://www.gwg.org/download.php?f=d6be762f2b5d729c65b15b9edd8b718a by the Ghent PDF Workgroup.
Anyway, I guess the original poster must have printed whatever needed