Well, I am aware this topic is already discussed in many places like
https://forum.kde.org/viewtopic.php?f=83&t=120522, but I don't
remember reading any relevant suggestion.

What I am talking about is adding a search box, which allows to search
menu entries from the application toolbar.

you could add one from the "Toolbar Configuration" dialog. this way we
don't have to worry about supporting other toolkits, since it is a kde
feature.

http://imgur.com/a/y2iTd
Here you see a google app with hidden menu bar and search functionality
in the toolbar. I think it simplifies the interface significantly.

What do you guys think, is it feasible?