Your dictionary will be easier to handle if the values are array references. Either do, $_ = [split /,/] for values %dictionary; or push them on in the first place.

Multi-word matching can be done by picking a key that can occur, eliminating its used characters from the sorted string and looking again. Backtrack if you have a residue which has no anagram.