Export a PDF, preferable aas PDF/X-4, but go to the output section and convert to output profile and choose the CMYK profile of your printer.
Or export as PDF/X-1a, if the don't accept files with live transparency.
This is for a newspaper ad, and the rep contacted me to say he needed me to convert it to CMYK and he did not state specifics about the profile of the printer
He should do so. Ask him about the output color profile he uses, convert in that. Without knowing that you have to guess, take one of your region which is given in the dialog, SWOP for US, FOGRA or ECI for Europe.
For newsprint it is important to us a newspaper profile like US Newsprint (SNAP). Newsprint has a very low total ink allowance to prevent ink offset.
You definitely shouldn't use a profile designed for coated sheets like the default US Coated SWOP. Assign a Newsprint profile like SNAP (Edit>Assign Profiles...), turn on Overprint Preview, check the color then export to PDF/X-1a, which will force all color into the newsprint profile. You can also export to PDF/X-4, but if you want all the color to be CMYK choose Output>Color Conversion>Convert to Destintion with the destination profile set to the same newsprint profile