Data structure or algorithm for quickly finding differences between strings
My solution is similar to j_random_hacker's but uses only a single hash set.

I would create a hash set of strings.
For each string in the input, add to the set $k$ strings.
In each of these strings replace one of the letters with a special character, not found in any of the strings.
While you add them, check that they are not already in the set. If they are then you have two strings that only differ by (at most) one character.

An example with strings 'abc', 'adc'

For abc we add '*bc', 'a*c' and 'ab*'

For adc we add '*dc', 'a*c' and 'ad*'

When we add 'a*c' the second time we notice it is already in the set, so we know that there are two strings that only differ by one letter.

The total running time of this algorithm is $O(n*k^2)$.
This is because we create $k$ new strings for all $n$ strings in the input. For each of those strings we need to calculate the hash, which typically takes $O(k)$ time.

Storing all the strings takes $O(n*k^2)$ space.

Further improvements

We can improve the algorithm further by not storing the modified strings directly but instead storing an object with a reference to the original string and the index of the character that is masked. This way we do not need to create all of the strings and we only need $O(n*k)$ space to store all of the objects.

You will need to implement a custom hash function for the objects. We can take the Java implementation as an example, see the java documentation. The java hashCode multiplies the unicode value of each character with $31^{k-i}$ (with $k$ the string length and $i$ the one-based index of the character. Note that each altered string only differs by one character from the original. We can easily compute the contribution of that character to the hash code. We can subtract that and add our masking character instead. This takes $O(1)$ to compute. This allows us to bring the total running time down to $O(n*k)$