Since Android Market turned into Google Play I have had nothing but random issues, ranging from the most common 'no connection retry' (on a 4G LTE connection? really, Google?) to the odd download error (usually 927 or 403). there really is no fix, clearing cache and such are merely placebos. just have to wait. when it happens you usually lost the connection to Google itself. their apps go through a proxy that goes down often--even Chrome will refuse to load websites when this happens, and you can often go into your account and sync and Google will show 'sync error'.
However, the new Play Store (not official yet, it's on Android Police) with the Material Design cues seems to work pretty well. none of the above errors yet.
"No Connection Retry" and "Connection Timed Out" are not related to the internet connection itself, but an indication you lost connection to the Google servers. your sync will show 'sync error' as well when this happens
"Could not be downloaded due to an error" is a random error code having more to do with Play Store taking too long to wake the Download Manager process and it times out giving that error. if you watch carefully, when this error happens before it does, you won't see the animated 'download' status bar icon at all. this means Google Play Store couldn't open the Download Manager app to initiate the download and failed. found that one out with a logcat on a rooted tablet. For reasons i have not failed to grasp as yet, Amazon is immune to that particular issue. it seems to flawlessly launch Download process properly.