Underestimation of work on Product Backlog Items

What is the impact of this underestimation? Is the Sprint Goal in jeopardy? What is the impact on the set of Product Backlog Items selected for the Sprint? What are the working agreements between the Development Team and the Product Owner? These are all important things to consider.

If the Sprint Goal is in jeopardy, then the Product Owner absolutely needs to be involved. Otherwise, I'd defer to the working agreements between the Development Team and the Product Owner to figure out what to do.

I wouldn't necessarily move anything back to the Product Backlog - keeping the items in the Sprint Backlog can help with a discussion at the Sprint Review and Sprint Retrospective with respect to what didn't get done and digging into why and how to improve for the future. Plus, as you mentioned, maybe the team will have time to get to some or even all of those other items.

As far as scope goes, the Sprint commitment isn't to scope, but a goal. If the Product Owner isn't willing to recognize that, I think they would need some in-depth coaching on more outcome and goal-oriented practices as opposed to output-oriented practices. There's definitely some room for teaching, and that probably falls to the Scrum Master.

(1) Does this mean that based on negotiation, the de-scoped items are moved back to the Product Backlog as soon as de-scoped or are these simply deprioritized within the Sprint Backlog while Development Team continues to monitor its progress with the possibility of being able to on these eventually (if at all found to be possible in due course within the Sprint cycle as it learns more)? If it so happens that the de-scoped items could not be completed anyways by the end of the Sprint, then these get sent back to the Product Backlog post Sprint Review?

They can move it back to the Product Backlog if they believe they can't turn it into a "Done" Increment. This can be done early on if it is so obvious, and doesn't have to be at the Sprint Review. The only thing to remember is that when you remove scope, it should not endanger or make the Sprint Goal obsolete.

(2) What should be the Scrum Masters action if the Product Owner is not willing to negotiate the scope and is adamant on having all items completed as selected during Sprint Planning?

Coach the Product Owner on whether output matters or if outcomes matter. Educate the PO that the work planned for the Sprint is just a forecast and committment is towards meeting the Sprint Goal. The PBIs selected for the Sprint should not become a contract or Sprint committment.

Does this mean that based on negotiation, the de-scoped items are moved back to the Product Backlog as soon as de-scoped 

My advice is not to think of items as moving between backlogs at all. It's a useful metaphor but it's also a bit misleading. 

The Product Backlog ought to show all of the work that remains to be Done for a product. In other words, just because something is planned into a Sprint Backlog does not strictly remove it from the Product Backlog. It shouldn't be removed until the work is Done, although estimates for the work remaining ought to be updated while it is in progress.

What should be the Scrum Masters action if the Product Owner is not willing to negotiate the scope and is adamant on having all items completed as selected during Sprint Planning?

I'd invite the PO to reflect on the joint commitment agreed during Sprint Planning. Was it to achieving the Sprint Goal, or to complete a forecast of work which will not then evolve?

The Product Backlog ought to show all of the work that remains to be Done for a product. In other words, just because something is planned into a Sprint Backlog does not strictly remove it from the Product Backlog. It shouldn't be removed until the work is Done, although estimates for the work remaining ought to be updated while it is in progress.

When the work in the Product Backlog is complete, which is when the above states that it gets removed from the Product Backlog, are the list of features delivered tracked elsewhere so that it's known what Product Increments have been completed till date. In other words, are we only tracking the work to be done via the Product Backlog or are we also tracking the work completed in some other artifact or perhaps just marking the item as closed within the Product Backlog but not necessarily removing it? 

The goal of Sprints is to deliver a potentially releasable increment at the end of each one.  That does not mean you have to release at the end of each Sprint. So you can track previously completed work as part of the increments being produced and release when there is a need/want to do so.  

How you want to track work that is completed is entirely up to you.  Scrum has no guidance for doing so.  Scrum is focused on getting work completed to meet the Definition of Done and delivering increments of value to the stakeholders for feedback. I think the real question is why do you want to track completed items?  I'm not trying to say it is bad to do so, but knowing why you want to track it can help you determine how/where to do the work.  For example, if you are trying to track for purposes of doing cycle time, cumulative flow or other such metrics, then you may not want to keep a list of the actual items but of data from the items as they move through your workflows.  But if you really have no answer to why you want to track them then maybe it would just be unnecessary work to do so.