There's a lot to be said for going with the simplest, most intuitive solution. Stackoverflow is a programmer community so people are pretty comfortable with this "Markdown" markup.
But to make it more accessible to the average person who isn't used to bothering with markup of any type, then the most basic solution may be best, so there is absolutely minimum difference between what they see as they type it in, and what it turns out to be on the site. Something along the lines of
$html = "<p>"
. preg_replace("\n\r?\n", "</p><p>", htmlspecialchars($text))
. "</p>";
It doesn't have any formatting except that a blank line creates a paragraph break, but depending on the audience, for example if it's a general audience, you may find that this is a better idea. If you give non-technical people a markup syntax for formatting, you may find that it either confuses them and they use it incorrectly and mess something up, needing help, or you may find that they go overboard on the formatting, using as many text styles as they can.
In my role I maintain a MediaWiki wiki as an intranet for this company, and have noticed that in general, while having a wiki is a great idea, its markup language is just not suitable for a general non-technical audience, many of whom prefer to write things up in MS Word, because that is familiar to them, and then upload the Word document to the wiki instead.
The other option is a WYSIWYG editing control within the wiki software. It needs to be good, and as close to "actual" WYSIWYG as possible. It shouldn't be possible to get something looking OK in the preview which is messed up after filtering it server-side, because someone will find a way to do that.
How to allow non-technical people to create links between pages is another matter which you may find to be complicated.