I used 2 differents PMS (2 years ago and 1 year ago), loventis and cloud bed.
The price wasn't a problem, both had different price depending of your number of beds and that was great for a small hostel.
They were both SaaS application, accessible through the browser.
The things, I would have love to see or have, would have been to make it easy to tweak the bed or to upgrade any guest when they walked in, loventis was good for that and cloudbed a bit less (too much of Hotel thinking, not really for dorms).
Mobile app... or really responsive (like cloudbed), I was crazy when thinking about a possibilty of this feature... changing the bed, and in the same time allocating room on my phone, or being able to do thing from the kitchen or other common area without going to the office. I think that will be a game changer for small hostel.
And as you said some CRM features, I remember two years ago I was sending custom emails to each of the guest to talk about the tours and activities before the checked in.
If you want to look into this kind of problem, you should look into myAllocator (also from cloudbed), it will connect all the OTAs for you, and you can concentrate on the PMS features.