I'd like to get all user profiles filtered by a specific property (department for instance) using REST. Is that possible? In my dreams:
Yes, it is possible, but you need to use slightly different approach.
You can use search in order to filter users by profile property. Normally core profile properties are mapped to corresponding managed properties in search. If you are using custom profile properties, you need to make sure that this mappings exist or create it if it's missing.
Then you can run search query to find all people with profile property.
For example following query searches all people by acccount name mask:
B09A7990-05EA-4AF9-81EF-EDFAB16C4E31 is reference people search results.
Later you need to parse search result, grab
AccountName and then use rest to query particular user profile and extract properties.
A bit more samples and info here - Working with People Search and User Profiles