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.