Hey ich benutzte auch ein Android ohne installierte Google Dienste (Xperia V mit CM12) und ausschließlich FDroid Apps. Es braucht oft eine ganze Weile um sich zum ersten mal zu orten. Mit dieser App https://f-droid.org/repository/browse/?fdfilter=GPS&fdid=org.fastergps bilde ich mir ein das es etwas schneller geht.

Wenn es gar nicht geht, und auch ein neu-installieren von CM nichts bringt würde ich versuchsweise auf die Stockrom zurück gehen. Somit kannst du einen Hardwaredefekt (hatte ich auch schon!) ausschließen.

Falls das GPS mit der Stockrom geht, kannst du dir überlegen ob du auf eine andere CM Version oder eine ganz andere Custom Rom ausprobieren willst.

Ansonsten kannst meines Wissens auch mit dem xposed Framework das Stockandroid umfangreich anpassen und z.B sämtliche Google und Samsung Apps loswerden und eine Vernünftige Rechteverwaltung nachrüsten.