Minimal .apks for play store
Well... finding an old package, looking at those files I discovered the answer. Sometimes it takes very long to find it and the solution is simple.
Short Answer
You should also move &quot;Phonesky.apk&quot; to /system/app/ folder and then restart your phone.
Summary

Download the latest Play Store .apk (Try for example Android Police): http://www.androidpolice.com/2014/03/13/download-latest-google-play-store-4-6-16-with-new-require-password-option-tweaked-ui-forced-self-update-and-more/
Get the Gapps .zip for your system: http://wiki.cyanogenmod.org/w/Google_Apps
From this .zip, move these 4 files to your phone storage: &quot;GmsCore.apk&quot;, &quot;GoogleLoginService.apk&quot;, &quot;GoogleServicesFramework.apk&quot; and &quot;Phonesky.apk&quot;.
Use a File Explorer (like File Manager with root right) to move these 4 files to /system/app/
Install Play Store .apk (for example: cm.android.vending-4.6.16.apk)
Restart phone
Done :D

Edit: WARNING 2015-05-16
Even though this works, I now recommended just installing the whole gapps. Just now I tried to update my cyanogenmod to CM 11, which failed, but when trying to set my backup back, all was reset to the state when you just flashed CM (although the data was still there, so smart apps recognize this). This was solved by 1 of the following 2 things:

First flashing a clean CM 10.2, then restoring my backup with TWRP (if did this the trick, you can ignore this warning)
Flashing Gapps for CM 10.2: http://wiki.cyanogenmod.org/w/Google_Apps