Is the loss of closed Keplerian orbits in relativistic mechanics directly tied to the absence of the Runge-Lenz vector?
Yes, the two losses are directly related. As Goldstein explains, you can only expect a simple conserved quantity like the RL vector for degenerate cases like the Kepler problem, where $r$ is a single-valued function of $\theta$.
For the isotropic harmonic oscillator, motion is again periodic, and the corresponding conserved quantity is a tensor of the second rank, which also counts as "simple".
For other force laws (like GR), Goldstein comments that conserved quantities akin to the RL vector can be constructed, but "they are in general rather peculiar functions", since $r$ must be an infinite-valued function of $\theta$ for these non-closed orbits.
For these reasons, I don't see any obvious connection between the conservation of the Runge-Lenz vector and the periodicity of the motion. If you have some specific reason for suspecting such a connection, please tell us.