Это очень хорошо, даже если это неправильно, и вы не должны использовать регулярные выражения для разбора HTML.
Вы хотите сделать вторую замену в результате первой замены, а не в исходной строке:
String output = test.replace(Regex1, "<b>");
output = output.replace(Regex2, "</b>");
Вы можете заставить его работать для вашего примера, используя:
String Regex1 = "<a href.*?>";
Что делает квантификатор несвязным. Но это выражение легко сломается очень из-за малейших изменений во входном HTML, что (одна из причин) почему вы не должны использовать регулярные выражения для работы с HTML.
Некоторые простые примеры, для которых приведенное выше регулярное выражение не работает:
<A HREF="http://www.google.com">
<a href="http://www.google.com">
<a href="http://www.google.com"
>
<a href=">">