Just happened to me on rooted/unlocked Samsung S4 i545 Verizon CDMA standard size.
Symptoms: Update downloads from Play Store but no "installing" ribbon appears & nothing happens until finally notification arrives "cannot update [app name]".
Since I'm rooted I entered TouchWiz Recovery & erased cache & delvic cache. Also cleared Play Store cache & data. All had NO EFFECT.
SOLUTION THAT WORKED:
1. open Application Manager from inside phone settings. (swipe down from top edge of home screen & tap gear icon to open settings)
2. Locate Google Play Store. Press button "Remove all updates" and press "ok" when prompted to restore factory version.
3. Press "Force Close" button in Google Play Store inside Application Manager & tap "ok" after warning pop-up appears.
Done! No restart required. Play Store simply worked again!
All this suggests the problem lies with a buggy update by Google of its app. Thank goodness it now allows reversion to earlier factory version. I assume play store will update itself at a later date, hopefully after being debugged! If not, repeat the dose outlined above.
Added protection for rooted phone: Install Titanium Backup if you don't already have it, back up the old Play Store & preserve it. Then you can manually reinstall it.
EDIT: Google updates Play Store to the latest version almost immediately. If you want to make a backup using Titanium, then follow the backup steps listed above while disconnected from wifi & mobile data. Be sure to preserve the backup so it isn't auromatically deleted.
EDIT (2016-06-27): Backing up the old factory version of Play Store appears unnecessary. When Google updated Play Store back to the latest version (currently Build 6.7.13 E-all [0] 2920566), the installation bug did not reoccur. So either the process of reinstalling the old update did not break my fix, OR Google already had discovered and fixed the bug itself. Impossible for me to say. If anything further happens I will report it here!