As DanF stated in his comment, the common practice is to pay them for a service that included some non-Shabbos time, so we're not strictly paying for time on Shabbos. For instance:
Children's program: prepare posters or games before Shabbos, and use them on Shabbos.
Chazzan: prepare music before Shabbos and perform on Shabbos.
Caterer: often some of their setup will be done before Shabbos.
Babysitter: if you need one Friday night, it's best to ask him/her to arrive a few minutes before Shabbos, so that way you're paying for non-Shabbos time too. Similarly if you need one for late Saturday afternoon, have them stay until Havdalah, so they babysat on non-Shabbos as well.