The biggest error is usually around change over in the MSB. Do you see evidence of that in the 4000 readings?
No, the change from 511 to 512 is not an unusual step. One of the big challenges in fabricating an ADC is to make that true so the part will meet the DNL spec.
To maintain a DNL (Differential Non-Linearity) of under 1/2 LSB, the bin from 511 to 512 must not be less than 0.5 LSB or more than 1.5 LSB wide.
You will gain a small bit of accuracy by fits with more parameters than a single line but I don't consider the improvement worth the effort.
In the past, most ADCs used resistor ladders. Precision ADCs were expensive because it was necessary to laser trim the larger valued resistors to meet the DNL requirement.
Modern high precision ADCs use capacitor arrays. It is easier to maintain the proper tolerance in fabrication of capacitors with lithography. The array has caps with values C, C/2, C/4, C/8, ...
Since the large caps have a large area on the chip, it is easier achieve the required tolerance so laser trimming is not requied.