Question: can you begin a new paragraph with however?
Answer: Yes, you can start a paragraph or a sentence with “however.” I would certainly not mark it as wrong if it were used to show a contrast or exception to a previous assertion.