Actually, the only big difficulty with #4 is deciding what to do if you get a "word" that is longer than 80 chars.
Otherwise, you just split() the entire string on '\n[ \n]*\n' (i.e. two or more newlines, with any amount of whitespace between them.) You may have to play around with adding backslashes to get the newlines correctly into the regex engine itself. This give you an array (let's call it $document) with each element being a separate "paragraph".
Now, process each array element by splitting it on '[ \n]+' (any amount of consecutive whitespace--this would match \n\n, too, but there shouldn't be any such because that's what you used to split the string itself) This breaks up the paragraph into "words". (Call this array $words.)
Stepping through the $words array, create a new array called $paragraph.
Each elements starts out empty, and you append elements from $words to it, until the next "word" would cause the length to exceed 80. At this point, append a '\n' and then add the "word" to the next element instead.
Now just join() the $paragraph array together using a single space as the 'glue' parameter, and store it back into the original element of $document where it came from.
Finally, join() it using '<p> as the glue. I'm not an html lawyer, but iirc </p> is optional.
As far as #3 goes, you're right: it is easy, unless you decide to worry about whether the user entered an unbalanced set of start/stop tags.
