It's not you, it's Apple
First up of course, is making sure your issue is limited to iCloud. As long as your Mac can do other things online, and your iPhone still loads web pages and gets non-iCloud email, you're good. Then we move on to actual troubleshooting.
The first two rules of Tech Support are “Is it plugged in?” and “Is it turned on?” So let's start with the first: Check the Status Page from Apple to find out if iCloud is up and running right now. If it isn't, your troubleshooting options are limited until it comes back.
Now on to the second rule. Double check that your iCloud syncing is enabled and using the right account in these places:
(Yosemite) Mac: System Preferences > iCloud and make sure the right boxes are checked.
On iOS 8: Settings > iCloud > verify checked boxes.
Yosemite iCloud preferences, showing I have a lot of space still.
Time Traveller Tips
Also make sure your hardware syncs date and time info automatically, since mismatched time stamps can sometimes cause syncing issues.
(Yosemite) Mac: System Preferences > Date and Time
On iOS 8: Settings > General > Date and Time
When those are set up properly, try a reboot on the device that's causing trouble, particularly if you can verify everything's fine someplace else.
Preferences in iOS 8 for date and time.
Bring out the big guns
Should you still not find the culprit, there's a few options left to try. We can go with Melissa Holt's force syncing tip to kind of “kick” things into line, or if do you find repeat offenders, you can always try a solid troubleshooting tactic of logging out of your entire iCloud account, rebooting, then logging back in to see if that shakes things out.
If things have become so bad that you can't use the device, you might want to try making a full backup and restoring your device to factory settings or doing a clean Mac OS install, then NOT restoring that backup as a test to see if things improve at all. If they do, maybe there's an app you had installed or a setting that was keeping things from working properly, and that might be a troubleshooting exercise for another day.