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 usausada 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>