We manage to reproduce the problem and our developer findings indicate when you paste a link into Microsoft Excel, Excel prefaces the link with a byte order mark (BOM). When this link is loaded in the browser, it does not remove the BOM from the URL.
Upon loading the URL, the browser does several tests verify that the connection is secure (https) and this is failing due to the errant BOM. This ultimately causes the relay state error, since that parameter must be sent over a secure channel.
You can reproduce this problem by copying the cell and pasting it directly into firefox, thereby taking Excel out of the picture. This also fails (sometimes in a slightly different way) but suffers from the same root problem. If you remove the "https" from the pasted URL and simply retype it, you will notice that the link now works correctly.
This is a limitation in the fact that Excel stores the BOM in the URL, and the way in which the browser cannot interpret the BOM.
At the moment the only workaround we could think of is copy the URL link and paste it over to the browser and access the page.
Also, I would personally suggest you to raise a support ticket with Microsoft and I believe they might have better understanding on this issue to help you on this matter.
The official fix from Microsoft linked in the answer below worked for me: https://superuser.com/a/826003/74576
– Ryan – 2020-02-14T21:28:00.8833I ran into the same problem with a URL that requires authentication. If you click from an Excel spreadsheet to a URL that requires you to be logged in to a cookie-based session, most sites will redirect the Microsoft Discovery Agent to a login page. Unless the site is smart enough to redirect the login page request back to the original request in the case that the user is already logged in, you end up being forced to log in manually once the page loads in your real browser. The user experience is that all links appear to be logged-out. – Joe – 2013-07-10T04:43:18.603