So how do you create the candidates from within the text service? Well, the first thing you need is the original input, and you need to know what text was created from the original input. Almost all text services (there might be a few that don't do this) place the created text in the document, and attach the original input as a property associated with the created text.
Now, when you want to create the candidates for a given range, you get your property data from the range, look at the original input, and generate candidates based on the original input. Of course, you need to be in an edit session to do this.
Once you've finished creating the candidates, you can show them (outside an edit session) in some sort of modeless dialog or popup. Once you're done, you can replace the old text with the new text.