Здесь есть две проблемы. Сначала видимость по умолчанию должна быть указана в стиле. Но даже с этим это не будет работать, потому что привязка к триггеру сравнивает SelectedValue, объект ComboBoxItem со строковым объектом, и это никогда не будет эквивалентным. Для простоты примера я поместил соответствующие значения в свойствах тегов ComboBoxItem. Хотя фактическая реализация сравнения, скорее всего, будет зависеть от конкретных потребностей приложения.
<ComboBox Name="comboMyCombo">
<ComboBoxItem Tag="Hide">Don't show the label</ComboBoxItem>
<ComboBoxItem Tag="Show">Show the label</ComboBoxItem>
</ComboBox>
<Label>This is my label
<Label.Style>
<Style>
<Setter Property="Label.Visibility" Value="Collapsed"></Setter>
<Style.Triggers>
<DataTrigger
Binding="{Binding ElementName=comboMyCombo, Path=SelectedItem.Tag}" Value="Show">
<Setter Property="Label.Visibility" Value="Visible"></Setter>
</DataTrigger>
</Style.Triggers>
</Style>
</Label.Style>
</Label>