Was there a state or kingdom in North Africa before the arrival of the Phoenicians and the foundation of Carthage in 814 BC, except the primitive Capcian civilization?
Not really, no.
Carthage itself started out as a Phoenician colony, along with Utica probably in the 8th Century BC. The Phoenicians themselves were a Northwest Semitic people whose language was closely related to Hebrew and fairly closely to Amorite and Aramaic.
These western Phoenician outposts' main purpose was to help Phoenician traders manage the western part of their Mediterranean trade routes. As such, the fact that there was no major civilization there upon founding was actually a point in favor of the area. As it was, they still had to pay protection tribute to the nearby Berber tribes.
Throughout its history the city lived mostly off of trade (or its empire), and quite well at that during certain points. However, it appears the location wasn't really that useful to an ancient society without that trade flowing into or through it. There is a strip on the coast of North(west) Africa suitable for growing Mediterranean Climate crops, but it doesn't extend very far south of Carthage. So without that existing trade route to service, there wouldn't have been much reason for a civilization to develop there on its own, and the Phoenicians essentially founded those trade routes.
When Dido, the founder of Carthage arrived to the place, she purchased land from the Berber king Iarbas. Berbers kingdoms pre-date the founding of Carthage. Of course there were also other states in North Africa, see the comment of Semaphore. How "primitive" they were is a question of opinion.