On my mac, Command-K is the keyboard shortcut to erase all deleted messages (i.e., the Mail equivalent of emptying the trash), and has always been. There is no shortcut associated with "Add Link...". So, be careful not to just say "hit cmd-k, etc"...

Also, the use of the Add Link command forces one to use rich text, rather than plain text. If, as I do, one prefers plain text, not only the add link command doesn't work; the other suggestion to just control-clik and select "Open Link" also does not work, because the option is not there in the contextual menu (presumably because the text is not being recognized as a link).

There is, nevertheless, a service, buried under the Service contextual submenu, and called "Open URL", that does it. Adding a keyboard shortcut for it, one can do this with ease. But the original hint is better when there are more than just one or two links to check, imho.