There are a few possible fixes besides clearing the cache of the services and store:
Add another account to the device and use then when you access the Google Play Store.
Uninstall the updates for the Google Play from Settings > Applications manager > All > Google Play Services & Google Play Store > Uninstall updates.
Factory reset the device using from Recover or from the Settings menu.
One of this methods should work and the download functionality might be restored.