What variables are needed to calculate simple horseshoe orbit times?
That depends on the accuracy you want to work with. To zeroth order, as outlined in Murray &amp; Dermott, "Solar System dynamics", Chapt 3., you can do the following:


The zero-velocity contours that are plotted in your image will not be coinciding with particle orbits to infinite precision, but they're a good zeroth order approximation for objects with low eccentricity w.r.t the star ($v_{r}/v_{\theta} \ll 1$)
A particle on those orbits is on a regular Keplerian orbit of radius $r_{\rm H}$, out of reach of the gravitational influence of the planet at $r_{\rm P}$. Thus, to get the largest "chunk" of traveltime of one part of the horseshoe orbit, either inner or outer part, you can work out with relative velocities and the assumption of keplerian velocities.
Caution is required as to which orbital time you're interested in: If $a$ is Earth's distance to the sun, and the horseshoe is $d$ away from a perfectly circular orbit, thus alternating between distances $a\pm d$, then the orbital time in the rest-frame of the sun will be $v_{-}=\sqrt{\frac{GM}{a-d}}$, for a large number of orbits until close encounter, and after that $v_{+}=\sqrt{\frac{GM}{a+d}}$.
Therefore, the simplified case that the satellite is on its own Keplerian orbit is true for most of the time. Armed with this knowledge, we can approximate the Planetocentric recurrence time as $t_{\rm rec}=\frac{2\pi a}{v_{K} - v_{-}}$ as a simple catch-up time between objects on different orbits.
The relative velocity $v_{\rm rel} = v_{K} - v_{-} = \sqrt{\frac{GM}{a}}-\sqrt{\frac{GM}{a-d}}$ can be expanded in the limit of $d/a\ll1$ into $v_{\rm rel} \approx \frac{1}{2} \sqrt\frac{GM}{a} \frac{d}{a}$ and thus I derive from this $t_{rec}\approx \frac{4\pi}{\sqrt{GM}} \frac{a^{5/2}}{d}$. As expected, the cycle time diverges for $d=0$, as in the co-orbiting case with Earth this time must be infinite. An upper limit on $d$ cannot be derived from this, one would need to turn for the full solution for that.


Just out of curiosity, I've plugged in a few values into this formula and written something quick in python:

import numpy as np

#Basic physics quantities
G      = 6.678e-8 #cgs units
pi     = 3.141592
navo   = 6e23 # particles per mole
sigma  = 5.67e-5   #erg cm-2 s-1 K-4
kb     = 1.38e-16  #erg/K
km     = 1e5 #kilometers in cm
mearth = 5.98e27  #g
msun   = 2.0e33   #g
au     = 1.49e13  #cm
yr   = 365*24*3600
rearth   = 6370e5
rjupiter = 74000*km

#
# Returns the approximate horseshoe-cycle time in the reduced 3body problem
# Masses of bodies: m0&gt;&gt;m1&gt;&gt;m2
# Semimajor axis distance is from m0 to m1, radial distance is a(m0-&gt;m1)-a(m0-&gt;m2)
#
def hs_cycle(mcentral, semimajor_axis, radial_distance):
    return 4*pi/np.sqrt(G*mcentral)*semimajor_axis**(5./2.)/radial_distance/yr

#
# https://en.wikipedia.org/wiki/(419624)_2010_SO16 around the Sun
#
# Quoted cycle time ~350 years, with d=0.004 AU
#
print("Predicted 2010_SO16 cycletime [years] = ", hs_cycle(msun, 1*au,0.004*au), " predicted = 350 yrs")

#
# Janus/Epimetheus around Saturn
#
# a = 151410 km, d = 25 km, as stated in https://en.wikipedia.org/wiki/Epimetheus_(moon)
# Quoted cycle time = 8 years (from comments)
#
print("Predicted Janus/Epimetheus cycletime [years] = ", hs_cycle(95*mearth, 151410*km,50*km), " predicted = 4 yrs")


#
# 3753 Cruithne
#
# a = 1 AU and semimajor axis difference from https://en.wikipedia.org/wiki/3753_Cruithne
# Quoted cycle time = 770 years
#
print("Predicted 3753 Cruithne cycletime [years] = ",hs_cycle(msun, 1*au, (1.0-0.99774)*au), " predicted = 770 yrs")


and the results I get are

Predicted 2010_SO16 cycletime [years] =  495.7747141830971  predicted = 350 yrs
Predicted Janus/Epimetheus cycletime [years] =  11.542076781209305  predicted = 8 yrs
Predicted 3753 Cruithne cycletime [years] =  877.4773702355546  predicted = 770 yrs


So the formula may be off by up to a factor of ~2. This is for sure simply because reality is more complex than a simple circular-orbit approximation, but also due to the quality of the values used.
Wikipedia isn't well known for researching particular values well. I took those that I found there. For SO16 that was particularly confusing to select, so I took those two that were mentioned in the same line of text, hoping they would come from the same source.

Anyone finding more consistent values, is free to comment.