Either this is not a good example of the paradox of choice, or as I am more inclined to believe, the paradox of choice is mostly bunk.
While I don't discount that some consumers may be frustrated at times by an abundance of choice and may naively think their life would be better with fewer choices, I don't think reality would bear that out. Maybe easier in the moment of the choice, but less satisfactory in the experience of the outcome of that choice. I know my life would be measurably less enjoyable with fewer choices in all walks of life: fewer food options, fewer cities and towns to live in, fewer computer manufacturers, and yes, fewer note-taking apps. Fewer apps would not make the apps better. It would only remove some of the options that are satisfying niche needs for other people. It's a bit elitist to say there should be fewer of any category, because it implies that the subtlety of preference felt by others is unimportant.
Choice is the consumer side of the innovation process. If anything, the non-satisfaction with note-taking applications shows that more exploration, more innovation, and yes, more choices are in fact needed. Technology still has a ways to go before we have a robust approximation of the free-flowing paper and pencil note-taking, augmented seamlessly by the computer. We see where we're heading with things like OneNote, but we're still generations of innovation away.