Can the Play Store (in /system/priv-app/) be reinstalled with a newer version? Tapping on the build number in the Play Store doesn't really update it anymore on my device; I have no idea why. 
I've been trying to sideload the apk which just installs the newer version into /data/app/ but after several reboots i still don't see the newer version.

So yes, is it possible that I just delete the one from the /system/priv-app/ and push the newer version in it? 

Strangely, other Google apps that didn't come preinstalled just fails to install through the rom's old Play Store (version 5.5.12)and just comes up with a "-504" error. The same happens when trying to update preinstalled ones.

My phone is on stock Android 5.0 from the manufacturer rooted with SuperSU 2.82.
Yes and No, it depends on the version of thd play store and the Google play services, both usually work together and can not work with the wrong version, so try to replace both apps... 

You should use OGapps ( Open Google Apps ) , it's designed for custom ROMs.

You might have problems with the version designed only for DATA installations, and may need an alternative app from another custom ROM that is the same version.