Feasibility: train a model to learn how to extract data from documents
Both of the answers from FelixGK and Wargream have merit.  With the information you have posted though, I am not sure you are approaching the problem with the right objective, so the expected solution may seem further away than it probably is.  

As FelixGK suggests, you should break the models down into a set of one-vs-the-rest binary classifiers, one for each label.

I am not sure what you mean when you state


  From my understanding this apporach would need like 20 labels for every training example. And also the prediction is also only "correct", if all labels are matching.


Do you expect one model to collect multiple data elements within a document and assign the correct label to the element?  This is probably difficult in a single model, but could be easier using some form of ensemble approach, like a set of binary classifiers.  If you want to try it all in one model, I would look at neural networks and specifically, a network that implements a SoftMax activation function in the final layer. This will allow you to produce a multi-class output with probabilities assigned to each class. When using softmax, you generally want to accept the result with the highest probability.