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](http://technet.microsoft.com/en-us/library/jj835095%28v=sql.110%29.aspx).  
Veja também esta explicação de como o [CLUSTERED INDEX funciona](https://www.simple-talk.com/sql/learn-sql-server/effective-clustered-indexes/)