Can we solve this problem more efficiently than trying all possible combinations
I am going to prove that a special case of this problem is NP-hard and hence we can not aim for a polynomial time algorithm for the general case (unless P=NP).

Assuming each word has length exactly 1. This means each word is only one letter and each sentence is a combination of letters. We are looking now for a set of at most $k$ letter that construct as many sentences as possible. In other words, we are looking for the maximum number of sentences that can be constructed with $k$ letters and hence have union at most $k$. This problem is very similar to the NP-hard minimum $k$-union problem and can also be proven hard using the NP-Hard maximum clique problem (See this question for more information). 

Note that heuristics can be used to improve the running time if you are not looking for an optimal algorithm. However, a better greedy heuristic than sorting the words from the largest frequency is looking for sentences with the shortest total lengths and high number of intersections with other strings. In this case however, it would only make sense if your algorithm breaks before trying all possible values.