You won't be able to display popups from only a map service. It sounds as if you have an organizational account, which will allow you to upload feature services with more than 1000 points. If you had published both the feature service and map service together at the same time, you can display popups in the map service because the link is there to the features through the feature service. Since you published them separately, you can create a hosted feature service with all of your points and then enable popups for the map service, choosing to draw the feature information from your hosted feature service. Check this resource here, and scroll to the bottom of the page.
Hosted tiled map services do not support popups directly because the tiles are just "dumb" images. However, if you published your data from ArcMap and at the same time also enabled "Feature access" capability, this will publish both a hosted tiled map service and a feature service. Because the feature service has the attribute information, when you add the tiled map service to your web map, the system will automatically use the corresponding feature service when you enable popup information.
I published both a tiled map service and a feature service at the same time, added the tiles to my AGOL map, but still no popups (when I click the dropdown next to the layer name in Contents, there's no popup option). Am I missing something?