Question: What to do when a sprint is finished early?

At the moment our Scrum team works off stories from the backlog, if the sprint is finished early.

What happens with stories taken from the backlog? Will the stories be added to the current Sprint ? If yes, what if these stories won't be finished in time. Is the Sprint failed then?

Answer: 
Bring something from the project backlog into the sprint (after discussions with scrum master and project owner).

The size of the item you undertake will depend on how much time you have. If there is nothing small enough create a sub-task of a bigger task to get it started (ie do some of the preliminary work).

Alternatively create some tasks that make the code base better. I have never seen a code base that could not be improved in some way. Review some code add more unit tests etc..
Working on stretch or future sprint backlog items seems to be the common thing to do, which makes a lot of sense if your sprint backlog items are small enough and clearly defined. However, backlog items that may place the "done" code into a "no longer done" state should be avoided.

If the sprint is truly finished, tag it, prepare it for delivery, deliver it, and put your source code repositories into the "next sprint" state so there's no risk that late sprint changes will put delivery at risk.