I don’t see what’s “less than ideal” about using multiple links. See the StateCharter sample for an example where the user can draw multiple links from one single-port node to another one.
But having multiple designations of a single link is certainly a reasonable way to go. Do you have a small, fixed set of choices from which the user must choose? Or can they create as many as they like? Would you want to implement a multiline label, showing all the choices applicable to the link, and then have an editor for the label that has check boxes for each choice?
It’s better not to show important information in tooltips, because that makes it harder for people to understand without using the mouse, and because it prints less understandibly. I’m assuming that knowing the meaning/label text for each link is indeed important for comprehension.