With the algorithm currently used by cmark and commonmark.js, there is no efficiency cost to allowing multiline setext headers. We store successive lines in paragraphs, and when we hit one that looks like a setext header line, we just convert the paragraph into a setext header. No backtracking is needed. Indeed, allowing multiline setext headers would eliminate the need for a check we currently do (to see if only one line of text has been parsed).
I’m leaning towards thinking multiline headers are the best interpretation here. People who hard-wrap their text to a fixed column width may occasionally need these (although stylistically it’s generally best to avoid overly long headers). Currently there’s no way to do multiline headers in CommonMark (or Markdown generally), so the change would increase expressive power.