.Items.Add ではなく、.DataSource で指定するのは駄目でしょうか?

Private Sub Form1_Load(ByVal sender As Object, ByVal e As EventArgs) Handles MyBase.Load

    ComboBox1.DisplayMember = "Value"

    ComboBox1.ValueMember = "Key"

    Dim list As New Dictionary(Of String, String)()

    list.Add("001", "日本")

    list.Add("002", "アメリカ")

    list.Add("003", "中国")

    list.Add("004", "インド")

    ComboBox1.DataSource = list.ToList()

End Sub



Private Sub Button1_Click(ByVal sender As Object, ByVal e As EventArgs) Handles Button1.Click

    ComboBox1.SelectedValue = TextBox1.Text

End Sub

もし、DataSource を使わないのだとすると、恐らくは SelectedValue 経由での「設定」が
使えなくなるので、SelectedIndex で処理することになるかと思います。

Private Sub Form1_Load(ByVal sender As Object, ByVal e As EventArgs) Handles MyBase.Load

    ComboBox1.DisplayMember = "Value"

    ComboBox1.ValueMember = "Key"

    ComboBox1.Items.Clear()

    ComboBox1.Items.Add(New DictionaryEntry("001", "日本"))

    ComboBox1.Items.Add(New DictionaryEntry("002", "アメリカ"))

    ComboBox1.Items.Add(New DictionaryEntry("003", "中国"))

    ComboBox1.Items.Add(New DictionaryEntry("004", "インド"))

End Sub



Private Sub Button1_Click(ByVal sender As Object, ByVal e As EventArgs) Handles Button1.Click

    'ループで探す 

    Dim selectedIndex = -1

    For Index = 0 To ComboBox1.Items.Count - 1

        Dim entry = ComboBox1.Items(Index)

        If TypeOf entry Is DictionaryEntry Then

            If DirectCast(entry, DictionaryEntry).Key = TextBox1.Text Then

                selectedIndex = Index

                Exit For

            End If

        End If

    Next

    ComboBox1.SelectedIndex = selectedIndex

End Sub



Private Sub Button2_Click(ByVal sender As Object, ByVal e As EventArgs) Handles Button2.Click

    'Linq で探す 

    ComboBox1.SelectedIndex = ComboBox1.Items.OfType(Of Object).Select( _

            Function(Entry, Index) New With {Entry, Index}).Where( _

            Function(x) ((TypeOf x.Entry Is DictionaryEntry) AndAlso ( _

            DirectCast(x.Entry, DictionaryEntry).Key = TextBox1.Text))).Select( _

            Function(n) n.Index).DefaultIfEmpty(-1).First()

End Sub