I used to work for a Karaoke company. The type of disk you want to make is a CD-G. We used macs for everything from recording to graphics to invoicing. But we didn't for writing the text across the bottom. We used some old machine that was specifically dedicated to writing CD-Gs. Sorry, I can't think of what it was called, but I fear that you're out of luck (unless that machine used a unix os).
You could make Karaoke DVDs. In which case you would use Final Cut Pro and DVD Studio Pro.