Good point)
I like your solution. I think PriorityQueue fits very well into the purpose of this kata.

I suggest you to improve your solution by removing the nested class.
WordFreq object doesn't buy you anything, you just duplicate the data from map entries.
Add them to the entries to the queue directly instead.

It is mentioned in the question that sorting should not be used. I would prefer heap over it.