I feel like the core mechanics of the characters' platforming abilities wouldn't mesh especially well, Mario is all about momentum and precision while Kirby tends to focus on flashy attacks and such.
Surprisingly enough, I'm actually inclined to disagree. While it's true that both characters run through levels differently, the level design is largely the same, incorporating mainly open fields and gentle slopes, with relatively simple enemies being placed in clever locations. It wouldn't take very much to, for instance, make Kirby's Adventure levels compatible with SMB3 -- at the very most, all you'd need is to shift some enemy placement around and add a couple ladders and coin blocks.
And I say this after having already played Super Mario Bros. Crossover, where many of the characters definitely don't
mesh well with the standard SMB gameplay. But the problem there is that many of the added characters have projectiles, rigid movement, and are designed around much more threatening enemies that tank multiple hits; this creates a lot of awkward situations where you're sitting in one place spamming bullets against an enemy that can't reach you, or you're forced to make a jump that just doesn't feel comfortable at all with your character's physics. (In SMBC, unless customization and cheat options are selected, I would say that the Blaster Master tank is the only character that plays well for vanilla Super Mario Bros.)
In Kirby's case, movement is dynamic, just like Mario; and enemies are fairly simple, only taking one hit in most circumstances -- just like Mario. In fact, I'm not sure how many people know this... but the original Kirby's Adventure actually has momentum physics! The most obvious examples of this: if you jump while running down a slope, or you slide off of a ledge, you will actually maintain that momentum while you're in the air. Little tricks like this and others would definitely help Kirby feel natural in Mario levels, or vice versa.
But yeah, I honestly think a Kirby+Mario platformer would work, with only minor compromises necessary to either series' formula. It ironically makes more sense than a theoretical Mario+Sonic crossover, which arguably would
have level design compatibility problems due to the extensive use of roller coaster layouts which are staple to the Sonic franchise.
EDIT: One other thing I just thought of. I'm already sensing the potential counter-argument, "But can we really expect to fit in all of Kirby's trademark copy abilities in levels that just have standard Mario enemies?" No, and you shouldn't try to. Instead, new
abilities should be created that are specifically designed to synergize with Mario level design. For example: Koopas would offer the Shell ability, which could function sort of like a slower Wheel ability, but with slight differences in controls and physics -- namely, that it would ricochet off of terrain, just like Mario kicking a Koopa shell. Enemies like Monty Moles and Hammer Bros. might offer the Carpenter ability, which could be a projectile ability similar to Cutter or Bomb. Etc., etc.
As for Mario...? Well, obviously you gotta bring this power-up back.