python-docx отлично справляется, непонятно, что вам помешало это проверить, если вы его уже нагуглили.
чтобы не было проблем с кодировкой - используйте юникод.
# -*- coding: utf-8 -*-
from docx import Document
document = Document()
str=unicode("Тест", "utf-8")
p = document.add_paragraph(str)
document.save('test.docx')