Se tu perdeu a keystore da Play, infelizmente, já era. 😢
Não existe uma maneira de recuperar, inclusive, este é um cuidado que sempre devemos ter (fazer backup da chave). Por conta disso, eu geralmente prefiro gerenciar a chave manualmente (ao invés de deixar o Google fazer isso) e assim que crio o projeto, já faço bkp da chave.
Pior que realmente era a keystore, não pensei em fazer um backup quando publiquei o app, depois formatei meu pc, aí percebi que não tinha salvado a chave
Se tu tinha a chave na pasta do teu projeto, antes de formatar teu PC, talvez valha a pena tentar recuperar o arquivo, com um programa tipo o Recuva..