Isso ocorre pois ao clicar a primeira vez você chama a função `removerEstado()` e chama a função do click, na segunda a função já foi chamada e consegue ser usada a função de click.

O correto seria fazer o seguinte.

    $('#btn-remover-estado').click(function(){
        let estados = document.getElementById('lista-estados');
        estados.remove(estados.selectedIndex);
    });
    <button type="button" class="btn btn-danger" id="btn-remover-estado">Sim</button>


Ou

    function removerEstado(){
        let estados = document.getElementById('lista-estados');
        estados.remove(estados.selectedIndex);
    }
    <button type="button" class="btn btn-danger" onclick="return removerEstado();">Sim</button>