"Kage" means "shadow" and the first word relates to the COUNTRY they are from, instead of the village! So the "Hokage" is the "Fire Shadow" of the Leaf Village, which is in the Fire Country. Gaara is the Kazekage, or the "Wind Shadow" of the Sand Village which is in the Wind Country. "Suna" means sand, which is why the Sand Village is called "Sunagakure". (And the Leaf Village is called Konohagakure.)
If it helps, maybe think of it as ... "We went to the beach. We played all day in the SUN And sand!" suna = sun + a(nd sand).
For the second part of a compound, the initial (unvoiced) consonant may become voiced. There is no strict rule, you have to know the origin and meaning of the compound.
One example: if you take やま yama "mountain" and かわ kawa "river" together, you either get (1) やまがわ yamagawa "mountain river", or (2) やまかわ yamakawa "mountains and rivers".
Another example: the word ひと hito means "(one) person," but the compund ひとびと hitobito means "(several) persons". Usually Japanese makes no difference between singular and plural nouns, but there are some common exceptions.