Publishing your game (with it's APK) is done separately from setting up and publishing the game services. This allows you connect the game services to games on multiple platforms or to existing games which have already been published.
Just publish your game via the standard publish mechanism in the developer console (under All Applications
, click the Add new application button); this allows you to upload your APK.
Once this is done, you can setup and publish the game services (without an APK) from the Game services
section.
The connection between the game and the game service is established while setting up the game service (via the Linked Apps section). There you specify a package name that matches that of your APK and also provide the signature used for signing the APK. This allows your game to access the published game service.