No Laravel há um método que atende a tua dúvida e tu pode transportar.

Há uma função firstOrCreate que recebe dois parâmetros: attributes e values, ambos arrays. O que ela tenta fazer é encontrar no banco algo que satisfaça as condições do que você passar no primeiro parâmetro, caso exista, retornará o próprio objeto, caso contrário, criará um novo registro.

Ela é mais ou menos assim:

public function firstOrCreate(array $attributes = [], array $values = [])
{
    if (!is_null($instance = $this->where($attributes)->first())) {
        return $instance;
    }

    return tap($this->newModelInstance(array_merge($attributes, $values)), function ($instance) {
        $instance->save();
    });
}

Como funciona:

Nesse trecho da função, ele está fazendo uma consulta no banco com tudo o que foi passado como primeiro parâmetro da função firstOrCreate.

if (!is_null($instance = $this->where($attributes)->first())) {
    return $instance;
}

Por exemplo:

User::firstOrCreate(['email' => '[email protected]'], []);

A função irá realizar uma consulta no banco, verificando o seguinte: se, na tabela users, existe um usuário com email tendo o valor [email protected], então me retorne esse usuário. Caso contrário, siga o seu curso.
Para o seu caso: ['nome_cidade' => 'value_that_you_want', 'fk_estado' => 'value_that_you_want'].

No segundo trecho da função, ele vai apenas criar uma nova instância do modelo, tendo como atributos os dois arrays mergeados que foram passados e salvará no banco. Por exemplo:

User::firstOrCreate(['email' => '[email protected]'], ['name' => 'Dummy User']);

Caso o email não exista, o resultado será um novo registro no banco com esse email e esse nome de usuário.

Talvez tenha ficado um pouco mais complexo do que deveria por se tratar do framework, mas a ideia central é: realize uma consulta no banco na hora de criar o registro. Se existir um registro com as condições que satisfaçam o que você deseja, retorne o que for adequado para ti. Se não existir, insira o novo registro.