In the beginning, Kickoff had very limited searching capabilities that couldn't be even compared to KRunner and Lancelot. This was changed in KDE SC 4.4 when code from Lancelot's search was ported to Kickoff.
Still, although Kickoff now uses the same engine for searching as Lancelot, since it runs in the same process as the desktop itself, most data providers (called runners) are disabled to prevent unstable ones crashing the whole desktop. (even the calculator is disabled)
Lancelot runs in a separate process, so it can handle the risk of using potentially risky runners thus providing all the features KRunner itself does.
When browsing application tree in Kickoff, you can only see the currently open category, and to return to the previous one you need to click the 'back button'.
In Lancelot, you always have an overview of the previous levels you opened while browsing, and in addition, you have a breadcrumb bar.
In Lancelot, options for Logging out, Switching users etc. are accessible the instant you open the menu. In Kickoff, those are located in a separate section.
Lancelot provides quick access to both removable and fixed devices.
Apart from the look and feel which is completely Plasma themed, Lancelot sports a few other integration points from both developer's and user's perspective. One of the trivial examples is that Lancelot can be used as a 'Add widgets' dialogue alternative.
Although the initial sizes of Lancelot and Kickoff don't differ that much, making Lancelot's window smaller would render it barely usable which is not the case with Kickoff.
On the first start, Lancelot looks more complicated compared to Kickoff - two-columns plus section buttons versus one column that Kickoff sports.
Lancelot and KRunner are rather different programs - one is all-in-one application launcher while the other is only a searching interface. For that reason, only the searching experience will be covered in the comparison.
For navigating the search results, Lancelot uses Up and Down keys while KRunner uses the Tab key.
Lancelot uses the Tab key for the search box completion, while it also supports the End key used for the same purpose in KRunner.
KRunner sports a very sleek and simple user interface.
KRunner provides information about the syntax of each runner.
KMenu is meant to be a simple application menu meant only for easy application browsing. For anything more advanced, it fails short.
On the other hand, there are a lot of users who want only that - a simple menu from the days of KDE 3.x.