Los arrays en javascript parten desde el cero y tienen índices [0 ... length-1].
Tú estás haciendo un random que en ocasiones apuntará al índice [length], que no existe. (aunque esta posibilidad es minúscula y me sorprende que siempre te esté dando undefined.
DebierasPara asegurarte de no apuntar nunca al índice 4, debieras hacer:
var array = ["texto 1", "text 2", "text 3", "text 4"];
var random = Math.floor(Math.random() * (array.length-1));
$('a').attr('href', array[random].replace(/\s/g, "-"));
Pero esto no te va a dar un resultado equiprobable. En esa solución la posibilidad de que salga el texto 4 es ínfima.
Yo lo corregiría contemplando el caso de borde (random===array.length) y corrigiéndolo para apuntar al índice anterior:
var array = ["texto 1", "text 2", "text 3", "text 4"];
var random = Math.floor(Math.random() * array.length);
if(random===array.length) {
random=(array.length-1)
}
console.log(array[random].replace(/\s/,'-'));
PD: el nombre "array" es un muy mal nombre para un array.