A word puzzle can be something like a sort of game or puzzle where you try to find a secret message in mixed up words or things like that. It's a variety of types of puzzles and games using words. Riddles are specifically a sort of story with an answer you are solving for, but it's usually complete sentences and often in question format.
Good question, though!
It seems to me that "solved the puzzle" is best for a sort of puzzle which you may not have encountered before, and which has a single solution, while "finished the puzzle" is best for crossword puzzles and jigsaw puzzles, which can be thought of as a series of little puzzles which must be solved to finish the whole thing.