I never much cared for Force Palm, I always found it to be a bit of a... clunky move, I suppose you could say. Mainly due to the fact that he can't grab opponents in the air, even though other characters with Grab Specials (Ganondorf comes to mind) can. So giving him a new attack would be a nice change of pace, to me, at least.
Hmm... "Marshmellow Power" or Mega-Lucario... Eureka! Why not have him work in a similar fashion to how Goku works in Smash Flash, in that he gets a power up as a Final Smash (Mega-Lucario), but he can end it early in exchange for using a giant, stage covering attack that's an almost guaranteed KO (a buffed up version of his Brawl Final Smash)?
Something like "Bullet Punch" for his side-special would be neat, considering he is a steel type after all.
Bullet Punch would be a nice change, though, I honestly imagine that it world work in a similar fashion to Fox's Side-Special in that he zips across the screen. Better yet, he could use Bullet Punch as the initial attack, and like with Force Palm, grab the opponent and follow up with another attack such as Sky Uppercut, or even Drain Punch.
That, or they could always just give him Iron Tail.
A flurry of attacks as Close Combat would make a much better side-special in my opinion. I also think the Mega Evolution final smash is a shoe in.
Personally, I'd prefer this to be his Forward-Smash or even as a Jab combo rather than his Side-Special. The problem with making Close Combat a Special is the chance that it may yeild a similar aftereffect as it does in Pokemon games, which would hurt Lucario more than help, IMO.