Thanks @apol
I've built it from your branch and testing it now. Here is a list of issues I have faced so far:

@ngraham yeah this is the best way to go as it seems to me. What I did was just drawing attention to this problem since I cannot code and it's hard to understand how everything works for a non-coder.
@ltoscano I'd vote for any solution which makes Notes more configurable with respect to pasting of formatted text.

@ltoscano D22774 added the ability to choose between paste with and without formatting in the context menu, so yes, no problem with distinguishing.
Adding another shortcut like Ctrl+Shift+V is also a viable solution but these kinds (any kinds) of complex shortcuts have more chance to conflict with various things like input method switching (fcitx, ibus invoke or IM switch). One more reason to revive D14796 which was undeservingly abandoned btw. In fact, it won't (I've checked with fcitx/kimpanel) but that's another story.

Do those applications provide the paste-with-formatting action too?

No they don't. So it is one more thing that actually makes Plasma more feature-rich DE.

When you talk about "pastes text", "paste it", etc, which way do you mean?

Well, we're running in circles here. Until everyone here understands which paste options Notes applet has now and had before any discussion is useless.

Talking about cross-platform: Windows Notes app pastes text with no formatting, as Gnome Sticky Notes do, even Android apps do not use pasting with formatting by default.
Yep, I understand expecting pasting with formatting for Office apps, but for Notes widget it is more of an additional option.
I don't know how to explain it more clearly. Just suggest to copy some part of, say, Manjaro Linux forum main page and paste it with formatting no Notes. That's hardly a thing any user would expect to see in any notes applet on any platform.

Funny thing: I stopped using Notes due to this formatting thing so long ago that I cannot remember when exactly. There's a plaintext Kate file on my desktop instead.

@huftis
Having thought about this I guess I have my attitude towards the default Ctlr+V 'Paste' action: it should be without formatting. I can explain why. Notes applet is not an application. The reason it exists is to contain quick notes and tasks, memos, etc. Such text objects may come from various sources with heavy formatting, but Notes is not a web page or document processor, it shouldn't default to display potentially hard to read text (given the size of the applet) as a result of Ctrl+C - Ctrl+V pasting. Being not an application means it can behave differently in some aspects, that's why I find the comparison between this applet and other applications irrelevant.
But not only that. Open Kate pls and try to find "Paste with Formatting" there. Try to paste some text from this page there. You'll see there's no formatting. But Kate is an application, quite powerful one. And no formatting.
From the other side, having an way to paste formatted text is quite a neat option, that's why I guess it's better to have it untouched (I mean no reason to remove it).

This fails to build now.

I have no objections regarding default action, be it paste with or w/o formatting, it's rather a common sense fix: name what we use for Ctrl+V as "Paste", but and another action should get more detailed description. It also looks good in menu:

Thanks Nate :)
Actually it's rational to change documentHandler.pasteWithoutFormatting() handler as well, but I'm afraid I'm not good at coding to make such amendments.