Kelly opened the scoring from the penalty spot after Dons goalkeeper Jamie Langfield had been sent off for bringing down Borja Perez, and the midfielder struck from the edge of the area to double his side's lead in the dying stages.
It was the visitors who were first to threaten in the opening stages, with Gary Harkins playing a delightful flick to Perez, but the Spaniard sent his effort wide of the post.
Midway through the first half, Paul Heffernan sniffed out an opportunity for Killie as he seized upon a loose ball from a corner, but Andy Considine blocked his eight-yard strike.
At the other end, from a Johnny Hayes cross, midweek goalscorer Joe Shaughnessy came close to a second in as many games, his back-post header narrowly over the crossbar.
Killie were presented with a free-kick 20 yards out with 10 minutes of the first half remaining, but former Celtic man Cillian Sheridan could not take advantage, sending his left-footed effort curling over the crossbar.
But they took the lead from the penalty spot on the stroke of half-time. Perez ghosted his way into the area before being going down under the challenge of Langfield, and Craig Charleston had no hesitation in pointing to the spot.
Langfield was shown a red card for his misdemeanour and, with Rory Fallon sacrificed for substitute goalkeeper Jason Brown, Kelly stepped up to blast home from 12 yards.
The Dons had the ball in the net after 58 minutes, Magennis having won an aerial challenge with Bell and bundled the ball over the line, but he was penalised for his challenge on the goalkeeper, and the goal was chopped off.
Despite their numerical disadvantage, Aberdeen were having a right good go at their opponents, and with 67 minutes gone they were just inches away from the leveller, Magennis crashing a shot off the crossbar from 30 yards, with Bell left stranded well off his line.
And the keeper was at full stretch to turn a McGinn free-kick round the post two minutes later, after Pascali had brought Hayes down just outside the area.
But the game was won for the visitors with four minutes left.
A neat move down the left flank saw substitute Rory McKenzie, amid furious claims for off-side, cut the ball back to Kelly on the edge of the area, and the midfielder sent a low shot inside Brown's right-hand post.