Current consensus seems to be that cantillation marks as they are currently used originated around the 9th or 10th century CE, relatively recently in the history of Judaism. Cantillation itself has existed for a long while, but cantillation marks are a relatively recent means of codifying an otherwise opaque word-of-mouth (and potentially chironomical) system. There are very few facts about cantillation that are commonly held to be true, and there is a lot of debate about what the real history is.
This codification wasn't exactly early on in the history of Judaism - if it were, we'd expect to see more references to the marks specifically in the Talmud. Baruch Davidson, via Chabad notes that:
The use of the cantillation marks in current use dates to at least the 9th-10th century CE. This was the era of the Masoretes, meticulous scribes in Tiberias, Jerusalem and Babylon who worked to establish a precise common text, vowelization and cantillation for the Tanakh.
This is echoed by Cantor David Pincus:
Eventually, in the 9th century C.E. (in the "Common Era") a family of scholars in Tiberias codified a system of printed symbols which would indicate: 1) the grammatical phrases of each Torah verse, and 2) a series of notes for each sign.
However, this doesn't preclude the possibility of cantillation marks predating this time - it only serves as a claim that our modern cantillation originated around that time. It does indeed appear that other forms of cantillation, both borrowed and manufactured, existed before the 9th century, and originated out of a practice called chironomy, where hand-gestures were used to indicate how a part should be sung. But it's plausible that information on the exact origins has been lost; the Jewish Encyclopedia states:
Attempts have been made to reconstitute the oldest form of the cantillation by J. C. Speidel [et. al.]. ...their conclusions [outweigh] the probable.
So, there you have it. It would seem to have originated in the 9th or 10th century out of a desire to codify, and make a pass at standardizing, the way cant works.
As to the differences between Ashkenazi and Sephardic cant, well - cantillation isn't a part of the Torah itself, and doesn't necessarily have to stay fixed. Since there's no religious imperative to maintain universal cant in Judaism, it makes sense that different groups and regions would drift apart in cant at different times. (If you've ever been to services in differing temples, you'll know what I mean - many of the cants sound similar, and although frequently, are not always identical.)
More history for the curious: the origins of cantillation as a practice are not dated, and potentially aren't dateable at all. The Jewish Encyclopedia cites that:
The earliest reference to the definite modulation of the Scripture occurs in the Babylonian Talmud (Meg. 32a), where R. Johanan deprecates the indifference of such as "read [the text] without tunefulness and repeat [the Mishnah] without song."
So it's known that as a practice it goes back at least that far. Chabad holds a slightly less reserved view:
The tradition of the ta'amim by which the Torah is to be sung, however, is as old as the Torah itself. It was taught to Moses together with the vowels, as it is integral to the correct understanding of the Torah.
Either way, this establishes that the origins of cantillation itself seem disconnected from the origins of cantillation marks, which is tangential, but important.