Goodness, there has been some speculation over this ! From memory,some years ago people from the Oxford Dictionary went into the matter. The conclusion was that there had been a fad in the C19 fad for 'comically' misspelling words and OK was short for Orl Korrect ! The other favoured origin was that Martin van Buren a C19 US President was known as Old Kinderhook, hence OK. These two ideas come together. You can see how 'OK for President !' with the man's picture, for example , would make a punning slogan, combining the two, and there's evidence that he used OK in his campaign literature and a name for his campaign headquarters.
On its own the Old Kinderhook theory, though the dates of first usage of OK fit, doesn't make perfect sense without the other. After all, we wouldn't have used, say, JFK as meaning 'perfect' or 'just right' No politician's name would be synonymous with happiness or being 'just so' ! But one politician using a popular fad does, and here this one found a happy coincidence.