Se non ho capito male l'errore sta nella generazione dell'esadecimale, ottieni valori casuali errati per colpa del valore 255, che va bene per il calcolo di valori rgb ma non esadecimali.

codice:
function colora() {
    const elemento = document.querySelectorAll("#contenitore div")
    const numero = elemento.length

    for (let i = 0; i < numero; i++) {
        let colore = "#"

        for (let c = 1; c <= 6; c++) {
            let esadecimale = Math.floor(Math.random() * 16).toString(16)
            colore += esadecimale
        }

        elemento[i].style.backgroundColor = colore
    }
}

setTimeout(colora, 500)