Should I rewrite completely an extended paper?
A rewrite is a matter of how you an expand your manuscript. i am sure you can start by using the existing text and add whatever is needed. Once that has been accomplished, or during that process, you will get a sense of whether the new material requires some or complete reorganisation of the original manuscript. so there is no clear answer, yes or no, it will clearly depend on the original manuscript and the material you add.

To start by completely rewriting everything does not sound like an efficient method unless you feel such an approach will free your mind from constraints imposed by the old manuscript. As a rule, I would say use the old manuscript as a basis since complete rewriting would probably take much more time. I am sure certain parts of the manuscript could easily be modified while particularly the results and the discussions sections is where most of the work will be.

Regarding the self-plagiarism, it has become evident from posts on Academia.sx that this is seen differently in different disciplines. You need to check with colleagues in the discipline about this issue but the fact that there is a request for the product you aim to produce indicates that no such issues exist.