Without knowing more about the laser printer it's really hard to say. Unless it is Postscript, it is considered an RGB device and you'll get better results if you work in RGB and leave the file in RGB mode. This may be true even for a postscript printer if you don't have an accurate color profile for it -- CMYK is all device dependent.
Given the lack of information, I'd be inclined to suggest using the PDF/X-4 preset.
FedEx told me to use CMYK, not RGB. So I need to know which PDF preset to use and I'd sure like to know what all the presets meant.
Did they also give you a color profile? Without it, and a properly calibrated and profile monitor, you have little or no chance of matching the output to what you see on screen.
Color management is a very complex subject, but the book I would recommend for the non-techie is Real World Color Management. Very down to earth and full of straight-forward advice.
The X-4 preset is still probably the best choice here. It leaves the colors unchanged and embeds color profiles in case the printer or RIP can read them for its internal conversions.
FedEx Office generally prints to Canon digital presses using EFI DFEs (Digital Front Ends => RIP for digital printer) equipped with both Adobe PostScript 3 and the Adobe PDF Print Engine.
Our advice from Adobe is to use the PDF/X-4 .joboptions as-is for printing at FedEx Office.
Note that there is absolutely no need whatsoever to convert anything to CMYK in modern workflows. PDF/X-4 provides for ICC profile tagged RGB content as well as CMYK content with any ICC color managed content properly converted at print time. No need for you to convert anything!