Eh bien... en trouvant un vieux package, en regardant ces fichiers j'ai découvert la réponse. Parfois, il faut beaucoup de temps pour la trouver et la solution est simple.

Réponse Courte

Vous devez également déplacer "Phonesky.apk" vers le dossier /system/app/ puis redémarrer votre téléphone.

Résumé

• Téléchargez la dernière version de Play Store .apk (Essayez par exemple 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/
• Obtenez le fichier .zip Gapps pour votre système : http://wiki.cyanogenmod.org/w/Google_Apps
• A partir de ce fichier .zip, déplacez ces 4 fichiers vers le stockage de votre téléphone : "GmsCore.apk", "GoogleLoginService.apk", "GoogleServicesFramework.apk" et "Phonesky.apk".
• Utilisez un explorateur de fichiers (comme File Manager avec les droits root) pour déplacer ces 4 fichiers vers /system/app/
• Installez le fichier Play Store .apk (par exemple : cm.android.vending-4.6.16.apk)
• Redémarrez le téléphone
• Fini :D

Edit: AVERTISSEMENT 2015-05-16

Même si cela fonctionne, je recommande maintenant simplement d'installer l'ensemble des gapps. Tout juste, j'ai essayé de mettre à jour mon cyanogenmod vers CM 11, ce qui a échoué, mais lorsque j'ai essayé de restaurer ma sauvegarde, tout a été réinitialisé à l'état où vous venez de flasher CM (bien que les données étaient toujours là, donc des applis intelligentes reconnaissent cela). Cela a été résolu par 1 des 2 choses suivantes :

• Flashez d'abord un CM 10.2 propre, puis restaurez ma sauvegarde avec TWRP (si cela fonctionne, vous pouvez ignorer cet avertissement)
• Flashez Gapps pour CM 10.2 : http://wiki.cyanogenmod.org/w/Google_Apps