Meu código imprime às duas opção de if e else tanto em for e em while

Fala Breno, tudo bem?

O que acontece é que você utiliza || no primeiro if, ou seja, perguntando se a pessoa tem 18 anos OU está acompanhado, então se alguma dessas afirmações forem verdadeiras, o código continuará normalmente, mas nesse caso precisamos que ambas sejam verdadeiras para que o código possa continuar no fluxo normalmente. Então alteramos || para && para que seja obrigatório que ambas as condições sejam verdadeiras, assim ficando o seu código:

console.log("trabalhando com condicionais");
    const destinoPossivel= new Array ("Salvador", "Sao paulo", "Rio de janeiro");
    const idade = 15;
    const acompanhado = { acompanhado:[true,false] };
    const temPassagem = {Passagem : [true, false]};
    const destino = "Sao paulo";

        console.log("destino possivel");
        console.log(destinoPossivel);
        acompanhado.acompanhado = (0);

        let destinoExiste = false;

    if(idade >=18 && acompanhado.acompanhado == (0) ){
           // parte problematica
            for( let contador = 0; contador <3; contador++){
                if(destinoPossivel[contador] == destino){
                    console.log("a");
                    destinoExiste = true;
                    break;

                }else if(destinoPossivel[contador] != destino){
                    console.log("o");
                }
            }


        temPassagem.Passagem = (0);
        console.log("Vendido");
        console.log("Aproveite sua viagem");
            }  

    else{
        console.log("Desculpe tivemos um erro!");
        }  

Espero ter ajudado, bons estudos :D