<apex:page showHeader="false">
<style>
a.msglink{
 font-size: 100% !important;
 margin: 0 3px !important;
 color: #015ba7 !important;
}
</style>
 <apex:outputpanel rendered="{!$User.IsDowngrade__c}" style="margin:0 3px !important;font-sixe:100% important;">
  <apex:pageMessage severity="info" strength="3" summary="This is a test message. Please<a href=https://www.google.com class=msglink target=_blank>click here</a>to test." title="Link Notification" escape="false">      
  </apex:pageMessage>    
 </apex:outputpanel> 
</apex:page>

Note the following:

• escape="false"

• href=https://www.google.com and NOT href="https://www.google.com" 

• class=msglink to add style definitions