I don't get why に is used in addition to は in the following sentences.
指示詞 に はコソアドで始まる規則的な体系があります。
Concerning the demonstratives, there is a regular system (of words, i guess) that starts by コソアド.指示詞 に は二つの使い方があります。
There are two ways of using the demonstratives.
On a side note, is it always Xで that is used in combination with 始まる to mean "to start with X"?
に doesn't have to represent a physical location. The literal meaning would be X exists in Y but as English speakers we will tend to take this too literally. In this case the meaning is closer to X has Y and it is a commonly used pattern. Think of it as existing figuratively (This property (Y) exists in X).
As a beginner I remember learning the AはBがある pattern, but actually the AにはBがある is more common (or simply AにBがある). The first one means more like A is holding onto B, or owns B, while the second means more like B is something that A has permanently (or at least practically permanently). The reality is not quite as black and white as that. To me there are many cases where either one would sound natural (but your example is not one, since the grammatical rule is obviously permanent).
To answer the other question: Yes, in the meaning of "(The word) starts with X" the Japanese will always be Xで始まる
You are confusing the structure in your sentence with the structure when the subject is marked as the topic ie:
B は Aに ある
As mentioned in a previous question (What's the difference between には and では),
"は is used to highlight a noun as a topic, and when が or を follows the noun, it is replaced by は. When other particles (e.g. で、に、へ、etc.) follow the noun, は is placed after them."
Let's start with the normal structure, with no topic marker:
Aに Bが ある
If the writer adds は to mark the subject's location as the topic then we get:
Aに は Bが ある
が marks that subject (ie what exists)
に marks the location where it exists
(-> Based on this logic your sentence would be stranger without に rather than without は)
As for which particle is taken by 始まる (if I may rephrase the question slightly), it depends what you want to say. I think this is illustrated by the following sentences which I have taken from the Apple dictionary and SpaceALC (with some modification to the English to make the point clearer):
学校は4月8日9時から始まる｜School begins on April 8 at nine. (literally: starts from)
礼拝は祈祷 {きとう}で始まった｜The service began with a prayer.
展覧会は来週月曜日に始まる｜The exhibition opens on Monday next week.
個人的な実験として始まる | begin as a personal experiment
Note: This is not an exhaustive list of particles that go with 始まる, just some of the more common examples. Japanese does not always translate directly into English consistently (see first example). As shown in the comments by Chocolate below, there are other particles (and compound particles）which may translate into "with".
