CINNAMON Desktop
Instalar CINNAMON:

apt-get install kali-defaults kali-root-login desktop-base cinnamon

Desinstalar CINNAMON:

apt-get remove cinnamon

MATE Desktop
Agregar APT:

echo "deb  wheezy main" >> /etc/apt/sources.list && apt-get update

apt-get --yes --quiet --allow-unauthenticated install mate-archive-keyring

Instalar MATE de cualquiera de las tres formas que te propongo.
Instalar MATE base:

apt-get install kali-defaults kali-root-login desktop-base mate-core

Instalar MATE base con algunos extras:

apt-get install kali-defaults kali-root-login desktop-base mate-desktop-environment

Instalar MATE base completo:

apt-get install kali-defaults kali-root-login desktop-base mate-desktop-environment-extra

Desinstalar MATE:

apt-get remove mate-core

Corregir error, el menú de aplicaciones kali linux no aparece. Seguimos estos pasos en terminal como root:

leafpad /etc/xdg/menus/mate-applications.menu

Justo debajo de la sección Internet debes agregar esto:

<!-- Kali Linux Menu -->
<MergeFile type="path">applications-merged/kali-applications.menu</MergeFile>

Nos debe quedar algo similar a esto:

.....
 <!-- Internet -->
  <Menu>
    <Name>Internet</Name>
    <Directory>mate-network.directory</Directory>
    <Include>
      <And>
        <Category>Network</Category>
      </And>
    </Include>
  </Menu>   <!-- End Internet -->

  <!-- Kali Linux  -->	
  <MergeFile type="path">applications-merged/kali-applications.menu</MergeFile>

.....