Which phone? Does this happen on both wi-fi and mobile data? Is the Play Store set to download over wi-fi only?
Try going to Settings>Apps>All, select Google Play Store, and Clear Cache/Clear Data, then Force Stop. Do the same for Download Manager. Now try again.