Eu encaro a criação de índices como algo que requer uma abordagem de "tentativa e erro".
No entanto há regras básicas a seguir:
1 - Índices não acrescentam performance em tabelas pequenas.
2 - Muitos índices podem diminuir a performance nos INSERT, UPDATE e DELETE
3 - Os índices deverão conter poucas colunas.
4 - As colunas usadas nas clausulas WHERE e BETWEEN ou que participam em um JOIN deverão ser colocadas em primeiro lugar. As restantes colunas devem ser organizadas com base no seu nível de distinção.
Tendo isto em conta a resposta à sua pergunta é:
CREATE INDEX TESTE2 (Estado ASC, Cidade ASC, DataCadastro ASC, DataNascimento DESC)
No entanto, se a clausula ORDER BY DataCadastro, DataNascimento DESC for usada muitas vezes e prevalecer à ordenação pela chave primária , deverá equacionar-se a criação de um CLUSTERED INDEX nessas colunas.
Nesse caso criar-se-iam dois Índices:
CREATE INDEX index1 (Estado ASC, Cidade ASC)
CREATE CLUSTERED INDEX index2 (DataCadastro ASC, DataNascimento DESC)
Os dados passariam a ser gravados ordenados por DataCadastro ASC, DataNascimento DESC
em vez de pela chave primária.
UPDATE
A troca de comentários entre mim e o jean, levou-me a pesquisar mais sobre o assunto.
A utilização de um CLUSTERED INDEX num campo que não seja "sempre crescente" poderá originar tempos de INSERT mais elevados.
No entanto, as ordenações são sempre mais demoradas que um INSERT.
Deve-se avaliar a relação custo/beneficio.
No caso da pergunta, podemos garantir que o índice seja "sempre crescente" se DataCadastro
for do tipo DateTime.
Se você quer se tornar um expert na criação de Índices siga este link.
Veja também esta explicação de como o CLUSTERED INDEX funciona