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..
What my team does is pull tasks in from the backlog that are reasonably small enough to complete with respect to how early we finished. If we're done with *that*, we give our QA team time to catch up with their testing, and the developers get a "free day" - we can use this to look into other issues not related to the current sprint, topics we want to research, configure/reconfigure our environments, etc.

Don't put a whole ton of work in just because you've finished early. Stick to what your team has committed to do in this sprint, and if extra work gets finished, that's an awesome plus.