Sometimes self-explanations sound better than the bare facts!
Kluge (24. Auflage) says:
Hexe Substantiv Femininum, Standardwortschatz (10. Jh.), mittelhochdeutsch hecse, althochdeutsch hazissa, hagzussa u.ä.,
mittelniederländisch hagetisse. Aus westgermanisch haga-tusjO
(o.ä.) fem. "Hexe", auch in altenglisch hägtesse. Der erste
Bestandteil ist Hag, das an das Gehöft angrenzende, aber nicht mehr
voll zu ihm gehörende Gebiet. Außerdem scheint es - nach altnordisch
túnrida, mittelhochdeutsch (14. Jh.) zunrite "Zaunreiterin, Hexe" zu schließen -, dass in der germanischen Vorstellung von Hexen,
diese auf dem Zaun (oder Dachfirst) reiten. Der zweite Bestandteil
könnte zu voreinzelsprachl. dhwes- "Geist" gehören, vgl. litauisch
dvasià "Geist" und dehnstufig mittelhochdeutsch getwAs "Gespenst". Näher am Germanischen ist ein seit Augustinus den Kelten
zugeschriebenes übernatürliches Wesen Dusius, das auch in dem
westfälischen Wort Dus für den Teufel gespiegelt sein kann. Offenbar
handelte es sich um ein Wesen, das bis zum Hag des Gehöfts mächtig
war. Das germanische Femininum ist entweder ein weibliches Gegenstück
oder eine Frau in der Macht eines solchen Wesens, im Mittelalter ganz
in vom Christentum geprägte Vorstellungen gekleidet. (...)
Ebenso
neuniederländisch heks, neuenglisch hag.
And about Hag:
Hag Substantiv Maskulinum, erweiterter Standardwortschatz, obsolet (8. Jh.), mittelhochdeutsch hac maskulinum und neutrum,
althochdeutsch hag, hac Stammwort. Sonst mit n-Flexion
altsächsisch hago, hag maskulinum(?), altenglisch haga,
altnordisch hagi aus germanisch haga-/On maskulinum "Umzäunung
(umzäuntes Grundstück, Weideplatz, Hecke)". Außergermanisch
vergleicht sich lateinisch caul(l)ae femininum "Schafhürden" (aus
caholae), kymrisch cae "Gehege". Weitere Herkunft unklar. Die Sippe macht nicht den Eindruck einer altererbten Wortfamilie.
Ebenso neuniederländisch haag, neuenglisch haw, neuschwedisch
hage. Siehe zunächst Hagebuche und (stärker lexikalisiert) Hagestolz, dann mit anderer Lautform Hain und hanebüchen, mit Geminate Hecke (und Heck), semantisch abweichend hegen mit
Gehege und vielleicht Hexe, auf Umwegen verwandt ist Kai.
It would be very interesting to know the etymology of the other terms you named.