Когда нет других атрибутов:
$string = preg_replace('~<a href="[^"]+">~', '<a href="#">', $string);
В противном случае:
$string = preg_replace('~<a ([^>]*)href="[^"]+"([^>]*)>~', '<a \\1href="#"\\2>', $string);
Демо:
php > $string = 'text....<a asd="blub" href="orig-link" title="bla"> Link text </a> other text .....';
php > echo preg_replace('~<a ([^>]*)href="[^"]+"([^>]*)>~', '<a \\1href="#"\\2>', $string);
text....<a asd="blub" href="#" title="bla"> Link text </a> other text .....