The Owls boss - a former Forest trainee - saw Chris Maguire, Jake Buxton and Joe Mattock fire his side into what looked an unassailable lead, but late goals from substitute Marcus Tudgay and Paterson, to go with an earlier Jamie Mackie effort, saw Gary Brazil's side - who had skipper Danny Collins sent off - claw back an unlikely point, although it still stretched Forest's winless league run to 11 games.
Owls manager Gray made three changes to the side narrowly beaten by Leicester as Giles Coke, Miguel Llera and Jeremy Helan came in for Glenn Loovens, Oguchi Onyewu and Caolan Lavery.
It took Henri Lansbury just 13 minutes to find himself in the book, cautioned when trying to bring down flying winger Helan in an uneventful opening quarter of an hour that was suddenly sparked into life by Wednesday taking the lead.
Collins was adjudged to have tripped Maguire in the box and the striker duly stepped up to drive the spot-kick past goalkeeper Karl Darlow for only his second goal in 14 games.
The Reds created their first real opportunity after 21 minutes when Mackie slotted a ball through for Derbyshire, whose first-time effort was kept out by the sprawling Chris Kirkland.
Wednesday countered with the lightning-quick Helan, who darted down the left wing before laying the ball off to Kieran Lee who fired narrowly wide.
Paterson worked some space for himself on the edge of the Owls box, but the finish was lacking as his grass cutter was easily saved by Kirkland.
Mackie then showed good determination down by the byline before being fouled by Mattock, who was booked, but Paterson's free-kick from a dangerous position came to nothing.
Forest, though, were once known as the kings of the counter-attack and they found a way back in to the match, with an equaliser on the stroke of half-time that would have had old boss Brian Clough smiling.
A great ball over the top from Lee Peltier saw Paterson scamper down the left wing and cut in to the edge of the Owls' box, before delivering the perfect cross for Mackie to powerfully head home.
But Wednesday hit back in injury-time, with Lewis Buxton heading in Maguire's corner to restore the visitors' lead.
Wednesday took a two-goal lead 12 minutes after the restart, with a routine fresh from the training ground. After winning a corner, Maguire pulled the flag-kick back to Mattock who took a couple of steps before firing a stunning low shot from 25 yards just inside Darlow's left-hand upright.
Shellshocked Forest tried to hit back and Mackie saw a shot deflected behind for a corner before the ineffective Henderson was withdrawn for Tudgay, making his first Reds outing of the season.
Leon Best headed two efforts over for the Owls as the visitors looked to kill off a Forest side struggling for ideas and inspiration.
A lapse from Darlow almost proved costly as his attempted pass to Gonzalo Jara went straight to Helan, but the Frenchman failed to punish the goalkeeper as he cracked a shot over the bar.
Forest, though, gave themselves a lifeline as Tudgay headed home after 77 minutes, with Mackie the creator after he had showed persistence to rob Mattock of the ball and send in a delightful cross.
Reds skipper Collins then saw red, collecting a second yellow for a bad foul on Maguire.
Then at the death Tudgay won a free-kick 25 yards from goal, which Paterson brilliantly curled over the wall and into the back of the net to silence the 1,788 travelling supporters.