You are not creating a new key and value pair, you are creating a new dictionary and saving in it variable, so its previous value is lost, since it cannot store two different values in the same variable.
If you want to add a new element you should create it through the standard dictionary syntax saying that you have a key that did not exist before and storing a value in the key and not in the dictionary. The key is like a different variable, that is, the dictionary is an object full of variables.
Another way is to use a method that the dictionary object has by default and it changes the object for you. Documentation.
cidade = {
'nome': 'São Paulo',
'estado': 'São Paulo'
}
cidade['país'] = 'Brasil'
cidade.update({'cep': '01000'})
print(cidade)
Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.