str_replace is great for replacements but you have a pattern to find and section of that pattern you want to reuse. In your example, you insert the ENTIRE original string back into each link. YOu also lose the name for description of the link.
A regular expression does the job when your needs are more complicated:
<?php
$txt="The quick brown #fox jumps over the lazy #dog.";
$try2 = preg_replace('/#([A-Za-z][A-Za-z0-9]+)\b/i','<a href="/user.php?u=$1">$1</a>', $txt);
$txt);
echo "\n\n".$try2;
?>
A quick explanation of this regular expression in case you aren't very familiar with them: /#([A-Za-z][A-Za-z0-9]+)\b/i
Find the # sign followed immediately by a letter followed immediately by 1 or more letters or numbers. Stop selecting the pattern when we reach a word boundary (\b). The first and last '/' slashes are delimiters. The 'i' at the end means to search without regard to upper or lower case.
The portion in parentheses will be held onto as areference. That reference ($1) in our case can then be used twice in the replace for the query-string parameter and link text. (Think of copy and paste. $1 is the first entry in the virtual clipboard.)
* This regular expression could be refined a bit but I'm going with this one for readability purposes.
Hope it helps!