Usar construtor parametrizado ou os métodos acessores?

Digamos que vc tenha uma agenda telefonica.

class Agenda {
    /* ... */
    public void salvar(Contato contato) { /* ... */ }
    public void deletar(Contato contato) { /* ... */ }
    public Contato buscar(String nome) { /* ... */ }
}

Numa agenda espera-se que um contato tenha um nome e um númro de telefone associado a esse nome. Não faz sentido usar uma agenda dessas pra gravar só o nome ou só o número, tem que haver os dois dados pra um contato ser considerado “consistente”.

class Contato {
    /* ... */
    public setNome(String nome) { /* ... */ }
    public setNumero(String numero) { /* ... */ }
    public getNome() { /* ... */ }
    public getNumero() { /* ... */ }
}

Se vc representar seus contatos como mostrado acima, vc ou qualquer um que for usar seu código, corre o risco de “esquecer” que um contato deve conter nome E número e fazer algo como:

Agenda agenda = new Agenda();
Contato contato = new Contato();

contato.setNome("Wellington");
agenda.salvar(contato); // salvando sem o número!

Com um constructor ficaria assim:

class Contato {
    /* ... */
    Contato(String nome, String numero) {
        this.nome = nome;
        this.numero = numero;
    }
    /* ... */
}

Usando um constructor e colocando nome é número como parametros pra ele, vc obriga (ou se obriga) a passar os dados necessário logo na instanciação do seu contato.

Contato contato1 = new Contato("Wellington"); // ERRO: Cadê o número?
Contato contato2 = new Contato("Wellington", "[telefone removido]"); // OK

Vc poderia salvar o contato2 na sua agenda com segurança, sabendo que ele possui todos os dados necessários para ser considerado um contato consistente. Já contato1 causará um erro de compilação.

Este é um exemplo bem básico mesmo pra exemplificar sua dúvida especifica; há várias outras coisas pra se preocupar como por exemplo:

• E se o nome ou o número forem uma string vazia?
• E se o nome ou o número forem nulos?
• E se o número não for um formato válido?

Enfim, cada problema pode ser tratado ali mesmo na construção do objeto, mas já é outra história.

Então serve para que um objeto a ser criado não fique sem sentido. Por exemplo: um objeto carro não pode ser criado sem uma marca e um modelo. Estou certo?

Seguindo meu raciocínio, sim.

private int codigoPaciente;
private String nome;
private String sobrenome;
private int idade;
private String sexo;
private int telefone;
private String endereco;

public Paciente(int codigoPaciente, String nome, String sobrenome, String sexo) {
	this.codigoPaciente = codigoPaciente;
	this.nome = nome;
	this.sobrenome = sobrenome;
	this.sexo = sexo;
}

Esse m eu construtor está correto? Pois não existe um paciente sem nome, sobrenome e sexo.

Sim. É por aí mesmo.