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..
For us a Sprint never ends early. We only increased our velocity or solved the problem in a way that makes us get more work done in the sprint. 

Saying that we always have a backlog of items that are prioritized in order of importance by our product owners. When any team can fit more work into the sprint it is very easy for them to see what to do next on the list that will fit positively into the sprints remaining time given their velocity. 

This avoids any downtime by the group waiting for discussions with Product Owner/Scrum Master on what should be done next. Our Product Owners and Scrum Masters keep on top of this list so there is always more work waiting to be put into the next sprint (or current one if time allowed.)