Your pupil is functionally the same as the aperture on a camera. Whenever light passes through an aperture, there is some diffraction that happens to it; the angle of the light changes. This is separate to anything the lens does. If there's too much diffraction, you won't be able to tell two different sources of light apart. The amount of diffraction depends on the wavelength of the light and the size of the aperture. Bigger apertures and shorter wavelengths diffract less. This "diffraction limit" has a formula accordingly.

So for the question, we make some basic assumptions: take the wavelength of red light as it's the longest wavelength for visible light, and assume he needs to be able to tell apart two light sources 2 metres apart at a distance of 15 miles to distinguish individual riders. We figure out the angle between two points 15 miles away and 2 metres apart and now we know the angular resolution necessary. We know that the diffraction limit of Legolas' eyes has to be at least as small as that resolution. We also know our wavelength, so we can stick those into the formula and find out the minimum aperture (ie, the minimum diameter of Legolas' pupils to make out the riders at that distance)

I don't know enough about eyeballs to be able to answer, but 5 leagues is a bit more than 5x farther than eagles can see, and eagles already have larger pupils than humans do.

Yes, the ability to see very far away does imply in very large eyes if you define "see" by properly focusing on the objects. But not large pupils, what matters is the size of the eyes lenses, on the bare front of them.

But no, he could be able to perceive those stuff without the larger eyes if he had a good mental model of how the horsemen interfere with the background (what is probably easier than it seems, because they would be moving), and how their hair would interfere with the previous outline.

many eyes are near the diffraction limit (for human sized eyes the diffraction limit is around 20/10 vision). To have better accuity you factually need larger eyes. Although it's the size of the lens that matters more than pupil size strictly. The pupil modifies the lens optics but the lens determines the limit.