I was FINALLY able to get Shopkick and a local school app loaded onto my phone by following the instructions above.
I uninstalled updates on both Google Play AND Google Play Services. This rolled back these two apps to the default version. (In my version of Android OS, I went to Settings > Apps > Google Play Store ... then click the 3 vertical dots on the top right of the screen and you'll see the option to "Uninstall updates". Do this...then do the same thing for "Google Play Services"). Uninstalling these apps may take a few moments and somem other apps that rely on these apps may start to freak out. You may get some "danger" notifications but it will clear up as soon as these apps are rolled back.
After doing this, I not only was able to search and find the apps (before, Google Play wouldn't even show them because they weren't "compatible") but I was able to load them and now use them.
This tells me that this issue is connected with the Google Play app.
btw...I had a Samsung Galaxy S7 that was an AT&T phone and had no issues. But I switched carriers to T-Mobile and even though my phone was unlocked, I was never able to get the AT&T version of the GS7 to work with T-Mobile's data.
So I sold my AT&T phone on Craigslist and bought the same phone but a T-Mobile version off Craigslist. This T-Mobile version of the GS7 had an updated version of Android OS (Nougat) compared to the AT&T phone I used to own. I had no problems with apps on the other phone but there were two apps (that I know of) that were not "compatible" with my T-Mobile GS7.
Now that I've gone through this process it seems likely to me that the problem is on Google's end...it has to have something to do with the updated softward, specifically, the updated Google Play and Google Play Services apps.
I hope this helps.
No joy here on an S7 Edge, after following all the suggestions, except for a factory reset (which I refuse to do because of the headaches involved in setting the phone back up, even from the backups I do regularly). I can't even side load the correct architecture app, as I get the oh so helpful message of "Application not installed." Not even a simple little error code is present to give an inkling as to what may be the issue.
The S7 Edge has been the best and worst phone I have ever had since my first phone, a Moto Razr. When everything is working, the device is great, but when things don't work as expected, I'd just assume throw the thing at a brick wall. Within my first year of owning this model, I've been through FOUR of these because of various hardware and deteriorating software issues. This device not compatible fiasco is just the most recent issue.