Paleo-Detectors are ancient minerals which can record and retain tracks
induced by nuclear recoils over billion year timescales. They may represent the
most sensitive method for the direct detection of Dark Matter (DM) to date.
Here, we improve upon the cut-and-count approach previously employed for
paleo-detectors by performing a full spectral analysis of the DM- and
background-induced track length distributions. This spectral analysis allows us
to project improved exclusion limits and detection thresholds for DM. Further,
we investigate the impact of background shape uncertainties using realistic
background models. We find that in the most optimistic case of a %-level
understanding of the background shape, we can achieve sensitivity to DM-nucleon
scattering cross sections up to a factor of 100 smaller than current XENON1T
bounds for DM masses above $100\,$GeV. For DM lighter than $ 10\,$GeV,
paleo-detectors can probe DM-nucleon cross sections many orders of magnitude
below current experimental limits. Allowing for larger uncertainties in the
shape of the backgrounds, we find that the impact on the sensitivity is
considerable. However, assuming 10% bin-to-bin shape uncertainties, the
sensitivity of paleo-detectors still improves over XENON1T limits by a factor
of $\sim 8$ for DM heavier than $ 100\,$GeV. For lighter DM candidates, even
with 50% bin-to-bin background shape uncertainties, paleo-detectors could
achieve sensitivities an order of magnitude better than proposed conventional
low-threshold experiments. Finally we show that, in the case of a DM discovery,
regions in which the mass can be constrained extend to significantly higher DM
masses than for proposed conventional experiments. For DM-nucleon cross
sections just below current XENON1T limits, paleo-detectors could constrain the
DM mass even if the new particle is as heavy as $ 1 \mathrm{\,TeV}$.