yourorder = yourorder.decode('utf-8') # или 'cp1251' или 'cp866' или что та у вас
district = district.decode('utf-8')
bot.edit_message_text(
chat_id=c.message.chat.id,
message_id=c.message.message_id,
text= u'{}Страна: {}\n\nВыбери товар'.format(yourorder, district),
reply_markup=key,
)