The question is quite broad, as exemplified by the statement: They may be insecure about their looks, their (odd) behavior, or may question whether they belong to a group (of friends, colleagues and what not).
Personally and anecdotally, I think that a healthy self-doubt forms the core of self-reflection and allows a social animal like Homo sapiens to improve its behavior and mold itself according to the social structure with all its rights and obligations.
To approach this question with a less opinion-based perspective, I think that the root of a possible answer is the question what happens when people lack any self-doubt. I'm not a psychologist, but narcissistic personality disorder (NPD) comes to mind. The characteristic features of this condition are dominance, arrogance, superiority, power seeking, and disregard of others. All these traits seem to fit a total lack of self doubt (Ronningstam, 2011). However, some phenotypes of this condition may include insecure people, but it is just for the purpose of showing what people may turn into that lack self-doubt (and admittedly oversimplifying NPD). The typical NPD sufferer therefore won't fit in well in a social structure, and humankind, obviously, has built highly complex social societies.
In terms of evolution, Joseph Henrich explains that long before the origins of agriculture, when humans expanded across the globe from the arid deserts of Australia to the frozen tundra of the Canadian Arctic, survival in the immense diversity of habitats depended not on specific genetic adaptations, but on large bodies of culturally transmitted know-how, abilities, and skills that no single individual could figure out in his or her lifetime. Even among foraging societies, humans show an immense variety of social organizations, group sizes, kinship structures, and mating patterns. He explains that this diversity is at least partially rooted in culturally-acquired and widely shared social rules.
- Ronningstam, J Psychiatric Practice (2011); 17(2): 89–99