Find all pairs in an array that sum to a given number
No comments on the time complexity, I do have a bunch of other comments:

Code to interfaces, not implementations

It's better to use Set&lt;Integer&gt; allElements = new HashSet&lt;Integer&gt;() (side note: guess you're not on >= Java 7, since you can use diamond operators otherwise) so that users of allElements do not need to know that it actually is a HashSet. This is just good practice. The lesson here is that it allows the programmer to replace the implementation with another in the future when required.

Does not contain, then add to a Set

In the following code block:

if (!original.contains(toAdd) &amp;&amp; !original.contains(reversePair(toAdd))) {
  original.add(toAdd);
}


I think the extra check !contains() is not really required because Set.add()'s Javadoc says:


  If this set already contains the element, the call leaves the set unchanged and returns false.


So, even if original did contain toAdd, calling add() will leave the set unchanged anyways. I guess this is useful when you're running on a large set of inputs so that there is some short-circuiting done, hence this is strictly just 'food-for-thought' and not something to frown upon.

hashCode()

I'm guess there's an implied range of inputs such as all must be positive right? Because your calculation (element1 + element2) * element2 + element1 will yield the same hash codes when element1 + element2 equals to 1, and having a bunch of negative and positive integers (or just 0, 1) will 'break' this easily. You may want to update your question with any assumptions on the range of inputs.

How to reverse a Pair

I think that you can move your method reversePair(Pair) into the Pair class itself as such:

public final class Pair { // also declared as final

    private final int element1; // also declared as final
    private final int element2; // also declared as final

    public Pair(int element1, int element2) {
        this.element1 = element1;
        this.element2 = element2;
    }
    ...

    public Pair getReverse() {
        return new Pair(element2, element1);
    }
}


Using it then becomes slightly easier:

if (!original.contains(toAdd.getReverse())) {
  original.add(toAdd);
}


Override toString()

Oh yeah, given how you want to print the contents of Pair objects in the end, why not just override toString() too? :)