Hi,

When I write links that point to Websites that is written in another language than the one refering to it; I usually add something like this:

This English Website links to the Norwegian newspaper <a href="http://vg.no/" title="Verdens Gang forsiden" hreflang="nb-NO" lang="nb-NO">Verdens Gang</a>.

This will make search engines understand that the linked Website is written in another language. - But how can I make the user understand that!?

I am thinking of some kind of grapical user interface to explain users that the link will lead them to a page written in another language. But I really cannot figure out a good way to do this. Need it for my private Website.

The search engine really aren't interested in your site telling them the URI language, For one it really doesn't matter what the language is at all. A sequence of characters may well be a word in some language somewhere, the SEs will use the indicators on the page to determine the language.
It obviously does no harm to include the attributes and may well be of a huge benefit to screen readers and other accessibility user agents, but do not consider search engines as a reason for doing so. In fact search engines should NEVER be a reason for doing anything.

How to tell users ?
Probably just exactly as you are doing, by having some text to tell them.

I am thinking of some kind of grapical user interface to explain users that the link will lead them to a page written in another language. But I really cannot figure out a good way to do this.

As with most things intended for users Keep It Simple!
Real usability is about making it so users do not need to think.