Google play says: "You need to use a different package name" - why?

The name of the APK doesn't matter, its the package name within the AndroidManifest file that counts.

<manifest xmlns:android="http://schemas.android.com/apk/res/android"
   package="com.yourcompany.yourapp"

There can only be one app on the market with that package name so in order to publish your ad free version you would have to change the package name in the manifest file, e.g. add the af onto the end of the package name within your manifest.

Regardless of the name of the .apk file, the package name of the Application contents inside it must be unique.

You can use refactor-rename to change this, though make sure that the change penetrates to the manifest file, proguard configuration, etc.

Apart from correcting app name in the Manifest I also had to change applicationId in the app's gradle.build file.

 defaultConfig {
    applicationId "com.example.changednameofmyapp"
    ...
}

Also, if you're using ProGuard, do not forget to change appropriate rules in your proguard-rules.pro

Just search the old package name in the whole project and change it.