We use spectra from CARMENES, the Calar Alto high-Resolution search for M dwarfs with Exo-earths with Near-infrared and optical Echelle Spectrographs, to search for periods in chromospheric indices in 16 M0 to M2 dwarfs. We measure spectral indices in the H$\alpha$, the Ca II infrared triplet (IRT), and the Na I D lines to study which of these indices are best-suited to find rotation periods in these stars. Moreover, we test a number of different period-search algorithms, namely the string length method, the phase dispersion minimisation, the generalized Lomb-Scargle periodogram, and the Gaussian process regression with quasi-periodic kernel. We find periods in four stars using H$\alpha$ and in five stars using the Ca II IRT, two of which have not been found before. Our results show that both H$\alpha$ and the Ca II IRT lines are well suited for period searches, with the Ca II IRT index performing slightly better than H$\alpha$. Unfortunately, the Na I D lines are strongly affected by telluric airglow, and we could not find any rotation period using this index. Further, different definitions of the line indices have no major impact on the results. Comparing the different search methods, the string length method and the phase dispersion minimisation perform worst, while Gaussian process models produce the smallest numbers of false positives and non-detections.