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*.  

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).