validation_curve differs from cross_val_score?
First of all, you have to shuffle your data because it seems that the model has learned a special pattern in the training data which has not occurred in the test data so much. After that, suppose that you get a validation curve like the current one. As you can see, Increasing the value of depth, does not change the learning. The two lines are parallel. In cases which each of the lines may have intersection, the upper line has negative slope and the lower one has positive slope, in the future on seen levels, you may want to increase the number of levels, not in this case.

Having same error, means that you are not over-fitting. but as you can see the amount of learning is not too much which means that you are having high bias problem, which means you have not learned the problem so well. In this case means that your current feature space maybe has high Bayes error which means that there are samples which have same features and different labels. Actually the distributions of different classes overlap.

There is something to argue about decision trees. If you have numerical features which are continuous, you may not have exactly same input patterns but they have overlap in their range.