Para validar os campos de um `select` você tem duas opções (que eu conheço).

A primeira delas é utilizando um `required` dentro da tag do `select` (o que você já está fazendo).

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-html -->

    <form id="form">
      <select name="Estado" class="form-control" required="required">
        <option value="">Selecione</option>
        <option value="RJ">Rio de Janeiro</option>
        <option value="SP">São Paulo</option>
      </select>
      <input type="submit" />
    </form>

<!-- end snippet -->

Lembrando que o `required` não é suportado pelo Safari (os outros é normal, só o Edge e o IE que é somente a partir da versão 10).

Caso queira fazer algo mais personalizado você poderá fazer de outra maneira. Veja o exemplo:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

    $('#estado').on('change', function(){
        $('#resultado').text(!!this.value);
    });

<!-- language: lang-html -->

    <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
    <form id="form">
      <select name="Estado" class="form-control" id="estado">
        <option value="">Selecione</option>
        <option value="RJ">Rio de Janeiro</option>
        <option value="SP">São Paulo</option>
      </select>
      <div id="resultado"></div>
    </form>

<!-- end snippet -->

A partir disso você poderia fazer uma personalização no estilo do formulário que está implementando. Veja:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

    $('#estado').on('change', function() {
      if (!!this.value == false) {
        this.classList.add('error');
      }
    });

<!-- language: lang-css -->

    .error {
      border: 2px solid #a94442;
    }

<!-- language: lang-html -->

    <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
    <form id="form">
      <select name="Estado" class="form-control" id="estado">
        <option value="">Selecione</option>
        <option value="RJ">Rio de Janeiro</option>
        <option value="SP">São Paulo</option>
      </select>
      <div id="resultado"></div>
    </form>

<!-- end snippet -->

Lembrando que nos exemplos eu usei um pouco de JavaScript "puro" e em partes com jQuery. Mas, você poderia fazer tudo somente com jQuery, mudariam poucas coisas.