def provide_str если юникод -- перекодируем cp1251 иначе отдаем как ес

def provide_str(s):
    # если юникод -- перекодируем в cp1251, иначе отдаем как есть
    if isinstance(s, unicode):
        return s.encode('cp1251')
    else:
        return s

# .............

print provide_str(k), ':', provide_str(v)