Создателям этот вопрос задавали и тогда они, наморщив лоб, выдали что-то типа того, что мол, это не мы криворучки, это питон такой.
В общем, сейчас, если установить с 3-м питоном, то всё будет работать на ура:
Сначала устанавливаем Питон 3.6:
sudo add-apt-repository ppa:jonathonf/python-3.6
sudo apt update
sudo apt install python3.6
sudo rm /usr/bin/python
sudo ln -s /usr/bin/python3 /usr/bin/python
После этого устанавливаем самый новый Autokey
git clone https://github.com/autokey-py3/autokey
cd autokey
sudo python setup.py install
Теперь Autokey будет нормально вставлять кириллицу в тексте, если в качестве метода вставки указать Clipboard Ctl-V
В Abbreviations кириллица по-прежнему не работает, но лично мне это не мешает.