Kidd, acquired Tuesday from New Jersey, looked out of sorts at times, committing six turnovers.
Meanwhile, Paul's dazzling performance on both ends of the floor had the enraptured crowd on its feet, raining down chants of "M-V-P!" for their own All-Star point guard while a banner offering similar sentiments flapped from the upper deck.
Kidd, who had practiced only twice with his new team, finished with eight points and five assists.
While Paul dribbled surgically through Dallas' defense, Peja Stojakovic and Bobby Jackson shot with precision from the perimeter, combining for eight of the Hornets' 10 3-pointers as the Hornets won their fifth straight.
Stojakovic made three 3-pointers and finished with 18 points, while Jackson hit five and wound up with 17 points. David West also scored 18 for New Orleans, despite playing with foul trouble in the second half.
Dirk Nowitzki led Dallas with 31 points. Reserve Jason Terry scored 14 points and Erick Dampier added 11.
Paul, whose nine steals tied a franchise high, scored 19 points in the third quarter, when he hit all seven of his shots, including a pair of 3-pointers, to help New Orleans surge to an 11-point lead.
New Orleans began to pull away when Stojakovic hit a jumper and Paul followed with an open 3 after Kidd got tangled up with two other players and fell. Soon after, Paul fed Hilton Armstrong inside for a three-point play, then Paul capped a 10-2 run with a pull-up jumper with just over a second left in the third quarter to give New Orleans a 75-64 lead heading into the final period.
New Orleans widened its lead to 17 in the fourth quarter, when Jackson made two of his 3-pointers and Dallas began to look tired and miss shots.
Neither team led by more than six during an intense but sometimes sloppy first half during which both teams turned the ball over 11 times.
[to top of second column]
Nowitzki and West each scored 14 points during the first two periods, but both also were called for three fouls.
Kidd made an immediate contribution on Dallas' first possession, feeding Josh Howard for a basket inside. However, he sometimes looked out of synch with his new teammates, who sometimes pulled him aside after unfruitful possessions and pointed out instructions.
Some of Kidd's problems had more to do with Paul, who set a franchise record for steals in a half with seven.
Dallas outshot and outrebounded New Orleans during the first half, but Stojakovic and Jackson each hit three 3-pointers and Stojakovic turned one of those into a four-point play when he was fouled. Paul then hit a pull-up jumper in the final minute of the second quarter, giving New Orleans a 47-44 halftime lead.
Notes: Shooting guard Morris Peterson returned to the Hornets' starting lineup after missing the Hornets' last three games before the All-Star break. ... Attendance was 15,941, about 1,300 short of a sellout. ... The Mavericks have dropped four in a row on the road and are 12-16 away from home.
[Associated Press; By BRETT MARTEL]
Copyright 2008 The Associated Press. All rights reserved. This
material may not be published, broadcast, rewritten or