A family of Microsoft word processing software products for creating web, email, and print documents.
You continue to overlook the fact that on the Layout tab of the page setup dialog, there is a setting for the distance of the header and footer from the top of the page. I previously included a screen shot of that dialog that showed the default settings of 12.7mm.
As I have pointed out in my response to Charles Kenyon's belief that that setting is irrelevant in Word 2013, once the Header\Footer pane has been accessed, as appatently it was in your case to remove the header, there will always be an empty paragraph in the header and footer and the distance of that paragraph from the edge of the page will be the distance specified on the Layout tab of the Page Setup dialog. If that distance is more than the margin setting, the margin can be offset.
While that may not happen on the computer on which the document was created, it will most definitely occur when the document is re-laid out on another device.
And that is why after you save the document as document y on the Android and then open that document y on the PC you then see the space being taken up by the header.
Here is a question for you: What do you mean when you say "when I remove a header I do so by removing the element itself"?
Once the header pane has been accessed, there will be an empty paragraph ¶ in it and you cannot remove it via the User Interface, or for that matter by accessing the document xml.