In my experience, Stan performance is decent with many models, particularly if all relevant operations are vectorized and the data sets are "reasonable." However it's easy to accidentally walk off a cliff, and write a model that takes days to fit. Additionally the real time output is a little lackluster, so it's hard to know how you're doing until it finishes (I hear they're working on that for ShinyStan).

I haven't done any HMMs or CRFs with Stan, but don't see why you couldn't do them. Passing in the data likely requires some tricks with arrays and indexing, but it's totally doable. Probably unlikely that you'd beat standard, custom algorithms, but if your HMM was part of a larger model, it might make sense.