[Magisk] BruceElliott:
I would just add my personal recent experience to Didgeridoohan's expert reply:

(1) This is something of a chicken-or-egg situation, in that some of the tools that you need to figure things out are in the Play Store, but you can't get into the Play Store to get the tools. You mention a message "unknown issue with google play service(s)." This happened to me and it is a nightmare. I will explain the method that worked for me, but it is a bit technical, as is this entire thread. (E.g., knowlege of adb, flashing TWRP recovery, the partition layout for your phone, rudimentary Linux command line, etc.) Also, it worked on a Samsung Galaxy S5 on Android 6.0.1; ymmv.

(2) First and foremost install TWRP recovery and do an image backup of all partitions. You can specify the destination of the image backup (e.g., internal or external SD card). Note that location and after the backup finishes (10 minutes or so), copy the entire backup to your PC for safe-keeping in case things go wrong. Worst case you can always re-flash TWRP and restore all partitions (but uncheck EFS partition if you need to restore; EFS is special). That should put your phone back to where it was at the time of the TWRP backup.

(3) The way that I got back into the Play Store, at least temporarily, was to delete Play Store data (settings...applications) and Play Services app + data. For Play Services, you probably only need to delete data; however "delete data" for Play Services on my system was greyed out. So I was stuck with either uninstalling both the app and data or finding this system app's data in the /data/system directory and deleting it from TWRP or adb. In retrospect things would have been much simpler by deleting Play Services data from TWRP or adb rather than completely uninstalling Play Services; but I was ignorant at the time...

(4) The phone will be very iffy after uninstalling Play Services because Play Services is a deeply embedded system app and many things are dependent it. So you should be prepared with an old factory stock ROM which includes gapps (gapps includes Play Services) in the /system partition. I flashed the old factory stock ROM to completely replace /system including all gapps (including Play Services and Play Store). I got the factory stock ROM from Sammobile; but that source is only applicable to Samsung phones. Note that factory reset will not do the trick as factory reset only wipes the /data partition and Play Services is located in /system (at least in a factory stock ROM). So... the tricky part of this saga is that you need to get back to an old version of Play Services that Google will recognize as old and let you into Play Store to update. The Play Store app is in /system. However, the real problem with my phone at least was the data associated with Play Services, which is in the /data partition. But all of your data is also in the /data partition. Best not to factory reset, which will wipe /data and require you to restore that partition from the TWRP image backup.

(5) After the stock ROM flash, re-boot and 0pen Google Maps. Maps or any other app that communicates with Google will put the Play Store into panic mode to upate Play Services. You should receive a warning notification (in the pull-down notification area) that "xyz will not work unless you update Play Services." If you click on the warning notification, it takes you to a Play Store download area which begs you to update Play Services. After Play Store updates Play Services, it may go further into panic mode and start updating all gapps and possibly all apps. Whether or not Play Store updates other things, you should be able to open Play Store. I went through the above-described process several times trying to figure out what was wrong with my phone's system. I could always open Play Store after following this procedure. Sometimes I could see all of my apps as usual. However, when Play Store discovered that my device was "uncertified" (read rooted/modified, etc.), it would allow me to open Play Store but would not show my apps. In the latter case, I could get to "settings" in Play Store and see "Device Certification: Uncertified" at the bottom of the settings page.

(6) If you get this far, continue with Didgeridoohan's extensive suggestions to recover from the "Device Uncertified" state. Depending upon how modified your phone is, you may get away easy by following the suggestions at the link below to "white-list" your phone by registering it with Google as a ROM developer's system. If not (e.g., if you need root), you may need to go the Magisk route:

https://www.androidpolice.com/2018/...-apps-uncertified-android-devices-heres-deal/

Good luck with the nightmare.