Interpreting this particular learning curve I plotted the learning curve using the false-positive rate (FPR) as the scoring function. The function was of course adjusted to reflect the lower FPR as the higher score. The resulting learning curve looks something like this:

What do I make of this curve? More samples is bad? But less samples would also mean over-fitting, isn't it?
To address one of the comments, here is a little more context. I am using a Random-Forest Classifier (so not a linear model). Also, the learning curve uses the StratifiedKFold cross-validator with shuffling enabled. The problem that I am solving is classifying static documents into one of two classes and therefore features are based on the properties extracted out of the documents. I have about 20 numerical features.
For completeness, here's a similar plot with accuracy score (default) as the scoring function.

 A: 
But less samples would also mean over-fitting, isn't it?

Assuming your training/validation/test splits are shuffled and random, this is not necessarily true.  Fewer samples can mean lower bias, but higher variance.  Your model must generalize solutions based on sparse information, rather than becoming overly opinionated based on spurious patterns in the input space.
You didnt mention what kind of data you have or what type of problem you are trying to solve, but it is entirely possible that your model overfits after 5,000 samples, in which case, you should stop training after it has seen those 5,000 samples.
I would imagine it is possible that your training data has a distribution of features/classes that is not optimal, or that you are using the wrong model to solve this problem.  Maybe you are using a linear model to fit non-linear data, maybe all of positive classes are in the first 5,000 training samples, etc.
A: Your second curve looks promising as it has low bias (high train score) and low variance (high test score "eventually").
Now you don't mention what kinda data you are working with. It is a binary classification problem, but is it a balanced dataset or an imbalanced dataset? If it is a balanced dataset, your second plot would be bang on and life's good! BUT if it is an imbalanced dataset, your second plot would be incorrect as we don't use accuracy for an imbalanced dataset.
As for the first plot, you say less data size would mean overfitting. I am not sure if I agree with that statement. Overfitting is when we have high variance (which is apparent from the later part of you plot as the train and validation score are far apart). I would say your plot is a good fit around 7000-8000 data size as it has low bias and low variance (relatively!).
