Проблемы с кодировкой, как исправить?
В python3 строки - юникодные, ord(c) возвращает unicode код символа, который только для ASCII символов будет в диапазоне 0-255 (0-127, точнее, 128-255 - расширенная латиница). Для кириллицы код занимает 2 байта.

Я не очень понимаю, что вы вообще делаете. Если конкретизируете, что именно за число должно быть, можно написать код (скорее всего, с гораздо меньшими извращениями).
Записывайте. Даю удочку. Рассказываю, как дебажить:

Смотрите каждое промежуточное и думайте, корректное оно или нет. 

Если действие сложное, развивайте на части поменьше. 
У вас вообще прямая функция и обратная. Это значит вы просто должны увидеть, в каком месте они начинают различаться.

Например, подайте на вход прямой функции текст "D(k¢B"...

А вообще, да. bin(ord(русска_буква)) будет больше чем 8 символов.