En esta entrada en mi blog, se explica el proceso completo para publicar una aplicación en el Play Store. Aunque es con la versión XE5 de Delphi, los pasos importantes son los mismos.
Ten en cuenta (y creo que ahí está el problema) que para publicar en Google Play no se puede utilizar la key de desarrollo.
Necesitas una cuenta de desarrollador (que imagino que ya tienes).
Realizar el Build para "release" y la configuración para "App Store".