¿Porque no la ejecutas sin descomprimirla? Por un lado te aseguras de que no tenga ningún problema intrínseco (que le falte un archivo, p.e.) y por otro no "rompes" el entorno de ejecución creado en el appimage. Solo tienes que hacer ejecutable el archivo y ejecutarlo. Creo que lo que te pasa es justamente que al descomprimirlo y ejecutarlo esta intentando usar el entorno de Python que tengas instalado en tu ordenador y, o no corresponde con la versión que Krita espera encontrar o le falta alguna dependencia. También puedes intentar instalar las dependencias que te falten, empezando por buscar en que paquete está el módulo "encodings" y, si vuelve a fallar, seguir analizando los errores para instalar la dependencias que te pide. Pero ten en cuenta que es posible que en los repos normales no esté la versión de Python que espera Krita y tengas que añadir repos de Debian Testing
Tampoco entiendo por que no usas el método normal de instalación desde los repos de MxLinux, que al estar basado en Debian debería estar tenerlo en ellos, aunque si es verdad que no va a ser la última versión (Debian Stable es una roca pero no está actualizado a la última).
Por otro lado, puedes tener en el menú cualquier archivo (un txt, mismamente) o ejecutable, solo tienes que crearle la entrada correspondiente editando el menú y añadiendo manualmente la entrada, que solo son accesos directos a un archivo concreto. Creo que existe también algún programa que te lo hace de forma automática solo metiendo el appimage en una carpeta concreta.
Espero haberte ayudado
