A couple of points.
A hypothetical simulation starts with a planet called Earth in a
perfectly circular orbit around a star called Sol. There is also a
moon called Luna in a perfectly circular orbit around Earth.
While a perfectly circular orbit isn't possible, it's true that you can mathematically define a perfectly circular orbit, treating the Earth as a gravitational point at it's center of mass and the Moon the same way. Orbits are often calculated around point-centers of mass because it's so much simpler and accurate enough, so that part is fine. You can have a perfectly circular orbit in a mathematical thought experiment.
Question: Can Luna's orbit remain perfectly circular or does it become
elliptical over time? At what point does it become stable? Never?
Thinking: The distance between Sol and Luna is not constant,
You're correct. While the 2 body system can (mathematically) remain perfectly circular, ignoring tides, gravitational lumpiness, etc, the minute you add a 3rd body, whether the sun or something much smaller, the perfect circle is no longer possible because the 3rd body stretches it. It creates a gravitational tug on the other 2 bodies. 3 gravitational body mathematics gets enormously complicated. See 3 body problem, so I won't get into that.
What you've assumed wrong is in thinking that the Sun or 3rd body makes the Moon's orbit elliptical. The circular orbit is already elliptical because a circle is an ellipse, just one with an eccentricity of zero.
When you add the 3rd body, it's gravity bends the shape into a kind of egg shape. It doesn't turn the circle into an ellipse, it turns the circle into an egg or it turns the ellipse into an elliptical egg or bent or stretched ellipse.
Thinking: The distance between Sol and Luna is not constant, it
fluctuates as Luna orbits Earth. Therefore the pull sunward also
fluctuates. Shouldn't this cause all moon orbits to eventually
deteriorate into longer and longer elliptical orbits until they
collide with the planet they orbit?
This, again, not really, no. Orbital deterioration is complicated and it mostly requires more than just a 3rd body tug, even a large tug like the one the sun gives the Moon. What the large close sun does is it reduces the Earth's hill Sphere. Planets closer to the sun for the most part have smaller hill spheres (see table) and the inner 1/3rd or 1/2 of the Hill Sphere is long term stable, so the sun doesn't destabilize Earth's moon at all, it merely jiggles it.
Orbits within the stable part of a planet's hill sphere can get bent by the sun, but they remain stable. The reason is that the tugs tend to balance out over time. Sometimes the Sun will bend the Moon's orbit more eccentric and sometimes it will bend it back closer to a circle. The net effect doesn't accumulate.
The mathematics or orbital perturbations is also very complicated. Earth's Milancovich cycles are orbital perturbations, driven mostly by the influence of Jupiter and Jupiter is not expected to ever destabilize the Earth. While obviously many collisions have happened, by now, most of the orbits in the solar-system are long-term stable.
So, back to the moon and onto Tidal forces, The Moon is moving away from the Earth at about 3.8cm per year because Earth's tidal forces tug the moon forward in a sense, which speeds it up and as it speeds up it moves into a higher orbit. Eventually if the Earth's rotation was to stay constant, in about 50 billion years the Earth would eject the Moon out of it's orbit. Because the Earth's orbit is slowing down and because the sun is going to explode long before then. For both those reasons, the Earth is not expected to lose the moon.
Tidal forces can operate either way on pushing an orbital further out or closer in. Mars' tidal forces on Phoebos are drawing Phoebos closer to Mars and in time it will crash into the planet or break apart into a ring system and more gradually crash into the planet. The varying factor is whether the planet rotates faster than the Moon in which case the tidal bulge is ahead of the Moon and pulls it forward and away, or if the Moon orbits faster than the rotation in which case the tidal force is behind the Moon and slows it down, pulling it in. When objects become tidally locked to each other, the tidal forces are largely minimized.
So, back to the point, the tidal forces that push the Moon away from the Earth, also tend to circularize the Moon's orbit, because the forces are greatest when the Moon is closest. If not for the sun, the Moon's orbit around Earth would be nearly circular. Tidal forces often circularize orbits.
So the Sun does tug on the Moon's orbit in the way you suggest and the Moon speeds up as it moves towards the sun and it slows down as it pulls away, giving it a lumpy orbit around the Earth. As the Moon moves further from the Earth it's orbit will grow more and more lumpy or chaotic, but it's not expected to ever get chaotic to the point that it will lose it's stability.
So in that sense, the Sun's gravitation is responsible for the Moon's eccentricity around the Earth because if not for the sun, that eccentricity would be nearly zero and nearly a perfect circle so the sun kind of does both. It pulls the Moon's orbit out of an ellipse, but it's also responsible for the Moon's eccentricity being what it is.
Below is a (perhaps somewhat exaggerated) picture of what the Moon's orbit around the Earth really looks like. This is because of the stretching and bending the sun does to the Moon's orbit around the Earth. It's not significant enough to pull it free, but significant enough to jiggle it pretty good.
Below are 2 pictures of Mercury's "cool" orbit that kind of spirographs around the sun. This is a more typical 2 body orbit, notice how much neater and closer to an ellipse it is than the ugly Moon orbit above. That's because it's still essentially a 2 body orbit not a 3 body. 2 body orbits are neat. 3 body orbits can get chaotic, stretched or bent, and the Moon is more than half way towards where it would become unstable and leave the Earth, so it's orbit is more unstable than most "stable" orbits in our solar-system, but it's still considered a stable orbit cause it's well inside the stable region of Earth's Hill Sphere.
As an FYI, Mercury's orbit doesn't neatly follow Newton's orbital laws either due to relativity and that was quite the puzzle to scientists for decades. The non Newtonian gravity accentuates Mercury's Spirograph orbit, pictured above but I used it, cause it gives a good example of a 2 body orbit over multiple orbits compared to our moon's jiggled orbit due to influence of a 3rd body (the sun). The point of all of this, is that elliptical orbits, (for the most part), are just as mathematically stable as theoretically/mathematically circular ones. Elliptical orbits aren't unstable nor are they an example of an orbit becoming unstable, they are stable, or at least, not unstable because they are elliptical. Some orbits are long term stable others are not, but the eccentricity isn't really a measuring stick for instability. The stable region of the hill sphere is a far better measuring stick. Both the orbits below, provided they are inside the stable region of the hill sphere, would be equally stable.
Hope that wasn't tldr.