Por que a função retorna o valor undefined

O problema principal no seu código é a comparação de arrays. Você não deve comparar arrays usando ==, pois o resultado não é bem o que você espera. Por exemplo, se eu comparar [] com [], deveriam ser considerados iguais? O JavaScript acha que não:

console.log([] == []); // false

Isso porque o operador == está seguindo as regras do Abstract Equality Comparison Algorithm. O ponto que nos interessa desse algoritmo, que consta na documentação, é:

If the operands are both objects, return true only if both operands reference the same object.

Em tradução livre:

Se os operandos são objetos, retorna true apenas se ambos referenciam o mesmo objeto.

E como arrays são objetos (inclusive, typeof([]) retorna object), e [] sempre cria um novo array, a sua comparação if (valido != []) sempre será true (não importando se valido está vazio ou não). E caso o array valido esteja vazio, o valor de valido[0] será undefined, pois como ele está vazio, não existe o elemento na posição zero (que é o que acontece quando nenhum número é encontrado).

Dito isso, acho que você está complicando o algoritmo à toa. Se a ideia é retornar o primeiro valor encontrado, esqueça esse array valido e use um return dentro do for:

function buscarDivisivel(array, num) {
    for (var i = 0; i < array.length; i++){
        if (array[i] % num == 0 && array[i] != 0){
            return array[i];
        }
    }
    // se chegou aqui, é porque nenhum número foi encontrado
    return "Nenhum número foi encontrado!";
}

var array = [10, 4, 7, 128, 42, -1, 0, 300, -5];
var num = 400;
console.log(buscarDivisivel(array, num)); // Nenhum número foi encontrado!
console.log(buscarDivisivel(array, 100)); // 300

Ou seja, se o número for encontrado, retorne-o (e o return retorna o valor imediatamente, interrompendo o for e a própria função, ou seja, todo o restante não será executado). Se nenhum for encontrado, ele nunca entra no if, o for termina e ele retorna a mensagem.

Se bem que eu particularmente não acho muito bom a função retornar um número ou a mensagem de erro.

Se nenhum número for encontrado, seria melhor ela retornar algo como undefined, por exemplo, para indicar que nada foi encontrado. Aí quem chamou a função que verifique o retorno e faça o que quiser em caso de erro (podendo até imprimir a mensagem, se for o caso):

function buscarDivisivel(array, num){
    for (const n of array) { // só para mostrar outra forma de fazer o *loop*
        if (n % num == 0 && n != 0){
            return n;
        }
    }
    // se chegou aqui é porque não encontrou nada
    return undefined;
}

let array = [10, 4, 7, 128, 42, -1, 0, 300, -5];
let num = 400;
let n = buscarDivisivel(array, num);
if (n !== undefined) {
    console.log(n);
} else {
    // não encontrou nada, imprime a mensagem
    // (mas eu poderia fazer qualquer outra ação, sem depender do retorno da função)
    console.log('Nenhum número foi encontrado');
}

Aliás, essa abordagem de retornar undefined é exatamente o que o método find faz (que foi uma das sugestões da outra resposta). Então ficaria assim:

let array = [10, 4, 7, 128, 42, -1, 0, 300, -5];
let num = 400;
let n = array.find(n => n % num == 0 && n != 0);
if (n !== undefined) {
    console.log(n);
} else {
    console.log('Nenhum número foi encontrado');
}

Inclusive, se olharmos na especificação da linguagem, veremos que find faz basicamente o mesmo que a sua função: percorre o array e retorna o primeiro elemento que satisfaz a condição (ou undefined, se nenhum for encontrado).

Claro que o fato de ter que chamar um callback para cada elemento do array faz o find ser um pouco mais lento, mas para arrays pequenos isso não fará tanta diferença assim.

Por fim, nos exemplos acima também coloquei ponto-e-vírgula no final das linhas. Pode parecer "frescura", e sei que o JavaScript "aceita" o código sem ponto e vírgula e "funciona", mas isso evita algumas situações bizarras que podem ocorrer se você não usá-los, como essa e essa (veja mais sobre isso aqui).

E discordo da outra resposta com relação a for com break ou return ser algo que não deve ser usado. Tudo bem que foge do escopo da pergunta, mas para uma discussão mais aprofundada, sugiro ler aqui, aqui e aqui.