Have you tried representing your strings as bit-strings. Maybe vec() and related are not the fastest, but Bit::Vector::Minimal or Bit::Vector could be useful.

You talk about unique pairs. If you don't have duplicated strings (which can be avoided via implicit normalization in your choice of representation or a cure such as 'sort -u') then any two strings make a unique pair. You have n(n+1)/2 pairs or n(n-1)/2 if you don't want the "diagonal" i.e pairs like (s, s).