is a "word prediction" problem, applicable using HMMs?
I think a HMM is overkill for this problem. You kind of have 'hidden' states, but they are very limited and dependent on the full sequence of previous states, which you probably want to avoid to make best use of the HMM's features. It also, as you rightly say, leads to a proliferation in states: each dictionary item adds as many states as it has letters to the model.

The way I would approach this it to use a trie which contains your dictionary, and then you traverse the trie as the user types characters. At each point you have a sub-trie which gives you the possible completions of the word. You could even (if available) augment this with probabilities to guess the most likely word (though this does not take into account the previous word in the sentence, which might be more useful).

If you want to learn about HMMs, one possible application would be a weather forecast (I thought this was an example Lawrence Rabiner uses in his tutorial, but it's actually on the HMM Wikipedia page). Or, if you want to work with texts, use parts-of-speech tagging. You want to have something where each observation can belong to several possible states (eg light can belong to adj, noun, and verb). Here you would have the words as observations and the part-of-speech tags as states, which keeps the model at a reasonably small size (and is thus easier to train).