When you wrote that you '...cleared cache' are you referring to the Play Store app cache or the system cache partition? They're two different things that affect different aspects of your phone.
Anyway, try going into your Settings >> Application manager, find the Google Play Store app, tap the 'Force stop' and then 'Clear cache' buttons; but also find the 'Downloads' and the 'Download manager' apps and do the same, 'Force stop' and then 'Clear cache'. Now start the Play Store app and see if this made any difference.