O. K. first appeared in 1839 (well before the Civil War) as 'orl Korrect,' a jocular alteration of all correct. In 1839 it was used in the political campaign of 'Old Kinderhook,' a nickname for Martin Van Buren.
1839- C. G. Greene, Boston Morning Post, "He...would have the 'contribution box,' etc. o. k. -all correct- and cause the corks to fly..."
1839- Salem Gazette, "The house was O. K. at the last concert, and did credit to the musical taste of the young ladies and gents."
1839- Philadelphia Gazette, " It is O. K. (all correct) in this quarter."
And many more in the same year in newspaper and magazines across the country. In those days, elections were serious matters, with fights in every saloon. Something said at a major rally would be repeated ad nauseum.

1840- N. Y. Morning Herald, General Jackson: "Tie up them papers," said the General, "mark on them 'O. K...."

The conclusion by A. W. Read in American Speech, vol. 38, 39 was that there was no evidence that the word was from Choctaw or Negro speech. This has been supported by most word students, although some of the thrown-together etymological and gee-whiz compendia continue to raise the issue. Variations such as oke, okay, okeh, okey-dokey, etc. are all later than O. K.

Och aye? No idea. Och is in both Irish and Scots, but the Irish seem to have overcome it to a great extent.
Derivation of the Oc in Langue d'oc from hoc is possible. Don't have the proper references for that, but I would not doubt a relationship.