What is the best way to tell people who were using the cloud service for free that it is going to be paid now?
1. Give ample warning. The time frame depends on what your product is and how difficult to replace it is, but I'd consider anything less than 1 month for a consumer product or 3 months for a business product to be unacceptable unless you're on the verge of bankruptcy or something.
2. Consider grandfathering in existing users. This doesn't need to be free forever, but X months free goes a long way towards keeping people happy. This can be combined with the previous point; for example, you could announce that new users will be paid only either immediately or starting soon, while existing users have X months free after which they will need to pay.
3. If applicable, give your users a way to export their data from your service before it goes paid. Even if most of them won't use it, it helps avoid feelings of lock-in or bait-and-switch.
4. General considerations for paid services: consider a free tier or free trial. Free tiers can be very effective when most users don't use many resources. It may or may not be appropriate for your case.
What I have seen companies do with good results is to put the free product into maintenance mode, then develop a new (and improved) product (even if it could be considered a "version 2" of the free product) and put a price tag on it from day 1.
But this is speaking from my observations, not from experience. I've never tried taking one of my free products and converting them to paid, personally.