1 - Is using 'escape = false' the only way to display a hyperlink in an error message?
Yes, otherwise it'll display as raw HTML.
2 - Is it ok to go ahead and use this technique in my scenario since only internal devs will be able to modify it?
As long as the messages cannot be modified or influenced by the user, this should be okay. If the user can influence the contents of the message, you're risking an "injection attack", where a savvy user inserts code that will be executed by someone else. This is the reason why you're not supposed to use escape=false in normal scenarios, to protect against injection attacks.
For example, let's say you wrote this code:
String someValue = ApexPages.currentPage().getParameters().get('message');
If the user were to write something like the following in their browser:
Then this message would display an alert when escape=false. This is innocent, but imagine a user sends a much more complicated script by email to an unsuspecting other user in the system. They could hijack the user's session, send out spam emails, change passwords, delete records, etc, whatever permissions they have, without even realizing something was wrong.
The point here is that if you use escape=false, you must make sure that you are using well-formed HTML, and do not allow arbitrary, unsanitized strings to reach the message, because it can be abused.
All that said... if only devs/admins can modify the messages, and there's no risk of injection, go for it. Just be aware that you should always carefully check your code to make sure that injection is not possible. Using escape=true eliminates the risk of injection, but obviously won't allow you to embed a hyperlink.
3 - Is the restriction on AppExchange products in place to protect consumers from a malicious App?
No, it's to protect users from apps that could be manipulated by users to hijack a user session. Apps are analyzed to see if they're malicious anyways, but this particular security vulnerability means that it's possible for user A to hijack user B's session just by modifying a record a certain way, sending an email, etc.
Even worse, if a non-user discovered this exploit, they could craft an email that has a link which, when clicked on by a user, could steal data, lock out users, etc. Injection vulnerabilities are a serious deal, so always make sure that you're only using it in a way where injection is impossible, such as using only static strings, sanitizing input using String.stripHtml4, etc.