Restrict iCloud in OS X

Do you have them use Office like 365 or something else? If so you could just block the mail and mac calendar app.

We've run into the same issue. Although I don't really see what all the concern is about, our global security folks are adamant about blocking iCloud access. For us, its blocked both with a Config Profile blocking access to the iCloud and Internet Accounts prefpane and access to iCloud services are blocked while on the company network.
Of course, this is a faulty set up since, as you mentioned, Apple integrates iCloud so deeply into the OS, that its possible to set up iCloud from multiple locations. If its been set up using one of those alt methods, once the Macs are off the network, iCloud syncing starts working, bypassing the original security intent. So its far from perfect.
I wish I knew a good way to remove the ability for setting up iCloud from within the other apps. Other than using Restricted Software to block them from running Mail.app and Calendar.app for example, I don't know of any good methods to do this. If you use Outlook for mail and calendar functions, you could argue that using Mail.app and Calendar.app are off limits and just block them altogether I suppose.

Maybe someone else has some thoughts.

I wasn't too concerned until the recent "your data will be taken off your device and put on iCloud servers automatically" announcement.

There is likely to be a few background processes running that you could possibly restrict via a config profile. You could also look at adding a DLP product like endpointprotector that can enforce rules on movement of company data between different cloud services.

If the devices are desktops, network filtering might be an option as well. Although it's usually difficult to work out what IPs to block, without crippling something else in the OS or MDM area.

Although not proactive in blocking the service, you can create an Extension Attribute to determine if an iCloud account is being used and then give that list to the Security team so that they can talk to the employee and remind them on company IT security policy.