LabelProvider is in fact the only clean way to go, but you need only one LabelProvider:
LabelProvider<MyObject> labelProvider = new LabelProvider<MyObject>(){
@Override
public String getLabel(MyObject item){
return item.getFrom() + " - " + item.getTo();
}
}
And assign it at ComboBox creation time:
ComboBox<MyObject> cb = new ComboBox<MyObject>(store, labelProvider);