Aha!
Now we are talking. And while we are talking, you probably don't want to brute force this, it's going to be slow as hell!

Again, put your word dictionary into a trie! Tries are perfect to match prefixes, which is exactly what you want to do. Next up create a list of all prefixes and their end positions, ie, at the beginning you have an n x n sized list one for each letter (and the matched prefix then becomes a letter). Each of these triplets looks something like this: (x, y, s) where x and y are the coordinates in the letter matrix and s is the already found prefix.

Now, go over every in the list and for each entry go over all adjacent letters (l) in the letter matrix and check s + l against the trie.
if s + l is a word, add it to the found word list
if s + l is a prefix to a word, add a new entry to the list with x and y being the position of l in the letter matrix and s being s + l

Rinse and repeat until you are done.

The rest is just iterating over the output to find the longest match, and tada you are done.
I would like to add that this idea isn't mine but comes from this StackOverflow question, which also contains some more possible solutions. You'll see a lot of tries there, which is due to the fact that tries are the perfect data structure for this sort of thing. Know your data structures