Find the best pairs of elements based on match weight
A couple improvements:

Pop from array and iterate over remaining items in nested loop

I tried to modify the nested for statements used to add to $possiblePairs and use a functional approach like with array_reduce() but instead found the example in this answer. Consider shifting (i.e. popping from the beginning) from the array to yield an array with the remaining elements with which to generate pairs.

while ($item = array_shift($elements)) {
    foreach($elements as $element) {
        //generate pair with $item and $element


With this approach, there is no need to keep track of counter variables (e.g. $i, $j), use those to index into the array, nor increment those until certain conditions change. It also makes the following line superfluous (so it can be removed):

$elementCount = count($elements);


Store pair as key, and score as value

This way the sorting can be simplified - using asort() with SORT_NUMERIC as $sort_flag. Then reverse the array for descending order using array_reverse().

while ($item = array_shift($elements)) {
    foreach($elements as $element) {
        $possiblePairs[$item.'_'.$element] =  rand(1, 100); 
    }
}
asort($possiblePairs, SORT_NUMERIC);
$possiblePairs = array_reverse($possiblePairs, true);


Output from keys

Because of the changes above, the keys are the pairs so use list() and explode() to unpack the pairs.

$used = [];
    foreach($possiblePairs as $pair =&gt; $score) {
        list($element1, $element2) = explode('_', $pair);
        if($score !== 0 &amp;&amp; 
            !in_array($element1, $used) &amp;&amp; 
            !in_array($element2, $used)) 
        {
            // save the pair to the output array
            $output[] = [$element1, $element2];
            // store the elements that have already been used
            array_push($used, $element1, $element2);
        }
    }
    return $output;


Another optimization

In order to only go through the  (last) foreach loop as few times as necessary, the following conditional could be added after pushing values into $used:

if (count($used) == count($elements)) {
     break;
}


That should prevent excess loop iterations. While the difference may be negligible for small lists, it may be very helpful to reduce the execution time for larger lists.

Demonstration

Check out this playground example for a demonstration. And compare the time output at the end with the original. 

| Run | Original             | Updated               |
|-----|----------------------|-----------------------|
|  1  | 0.0002138614654541s  | 0.00012707710266113s  | 
|  2  | 0.00021195411682129s | 0.00017905235290527s  | 
|  3  | 0.00021100044250488s | 0.00017690658569336s  |  
| Avg | 0.0002122720083s     | 0.0001610120138s      |


Here is the updated code:

function stuff($elements = []) {
    $output = [];

    // build an array with every unique possible pair
    while ($item = array_shift($elements)) {
        foreach($elements as $element) {
            $possiblePairs[$item.'_'.$element] =  rand(1, 100); // this would be replaced by a function calculating how closely the current elements match
        }
    }
    //use asort to sort on values and 
    asort($possiblePairs, SORT_NUMERIC);         
    $possiblePairs = array_reverse($possiblePairs, true);

    $used = [];
    foreach($possiblePairs as $pair =&gt; $score) {
        list($element1, $element2) = explode('_', $pair);
        if($score !== 0 &amp;&amp; 
            !in_array($element1, $used) &amp;&amp; 
            !in_array($element2, $used)) 
        {
            // save the pair to the output array
            $output[] = [$element1, $element2];
            // store the elements that have already been used
            array_push($used, $element1, $element2);
            if (count($elements) == count($used)) {
               break;
            }
        }
    }
    return $output;
}