In HTML4, you were encouraged to wrap form elements in some kind of block level element, like a P or a DIV, but thankfully in HTML5 that seems to have been dropped, so if you are using the latest doctype, then there won’t be a validation problem on that score.
Even if using HTML4, there won’t be a problem with leaving out the Ps. Just a validation message.
Typically the FIELDSET and LEGEND would go after the FORM start tag. That is one reason as to why it was recommended you wrap the thematically related controls and labels.