Hola,
Planteando el problema de otra forma, quieres que cuando se encuentre con #, muestre <br>#. Dicho de otra forma, quieres sustituir la cadena # por la cadena <br>#. Y para ello puedes usar str_replace() (
www.php.net/str_replace). Algo como:
Código PHP:
foreach ($LegArray as $clave => $valor) {
echo "<b>".$clave ."</b> tiene el valor de ". str_replace('#','<br>#',$valor)."<br>";
}
Saludos.