Despues de hacer varias pruebas, he podido comprobar que esto ocurre con la ISO de Kali Linux 2018.3 y ejecutar despues apt-get update y apt-get upgrade. Vamos, algo normal...
Pero si esta misma version la instalamos y no actualizamos, funciona correctamente. se pueden crear carpetas e iconos en el escritorio, desde el boton secundario del raton. ya que el menu contextual lo permite. Pero si actualizamos, el menu contextual cambia y ya no permite estas opciones.
Por eso pienso que es desde la ultima actualizacon on-line, ya que la ISO viene correcta.
Y por supuesto descargada de la web oficial de Kali.

un saludo,

Igual es la IU, prueba con otro entorno gráfico.
Yo uso KDE 64 bits 2018.3a y te puedo confirmar que me funciona correctamente. Estoy usando la versión 2018kde 64 desde el mismo día de la releasse y no encontré ningún problema.
De todas formas con la terminal tardas más o menos lo mismo. No es un gran inconveniente.

Mira a ver en los foros de Kali, igual encuentras algo