How do I have an enum bound combobox with custom string formatting for enum values?

ComboBox has everything you need: the FormattingEnabled property, which you should set to true, and Format event, where you'll need to place desired formatting logic. Thus,

myComboBox.FormattingEnabled = true;
myComboBox.Format += delegate(object sender, ListControlConvertEventArgs e)
    {
        e.Value = GetDescription<HowNice>((HowNice)e.Value);
    }

Don't! Enums are primitives and not UI objects - making them serve the UI in .ToString() would be quite bad from a design standpoint. You are trying to solve the wrong problem here: the real issue is that you do not want Enum.ToString() to show up in the combo box!

Now this is a very solveable problem indeed! You create a UI object to represent your combo box items:

sealed class NicenessComboBoxItem
{
    public string Description { get { return ...; } }
    public HowNice Value { get; private set; }

    public NicenessComboBoxItem(HowNice howNice) { Value = howNice; }
}

And then just add instances of this class to your combo box's Items collection and set these properties:

comboBox.ValueMember = "Value";
comboBox.DisplayMember = "Description";

You could write an TypeConverter that reads specified attributes to look them up in your resources. Thus you would get multi-language support for display names without much hassle.

Look into the TypeConverter's ConvertFrom/ConvertTo methods, and use reflection to read attributes on your enum fields.