iCloud password prompt on OS X Yosemite startup
If you have another Apple device, such as an iPad or iPhone, and you deleted iCloud off of it, it can disrupt every device you have, and you will just need to log in again, possibly generating App-Specific Passwords for your Mac. This happened to me around the same time, but I can't remember if it was the result of the upgrade to OS X 10.10.4 that broke the connection of it was when I deleted iCloud from my iPad (I was lending it to someone).

You may need to log iCloud in with your Apple ID password, or if that does not work, log in to your Apple ID and generate an App-Specific Password for iCloud. 

The same problem cropped up for iMessage/Facetime as well. There you definitely need to generate an App-Specific Password, however I think I resolved the issue with iCloud by entering my Apple ID password. Once it sets in your Keychain, you shouldn't see the pop up again.