Plugin: How should I handle deleting comments?

Do not delete the comment. One comment could have multiple children, and moving the replies up would create a false impression in any case.

The real question here is why someone wants to delete a comment and how you could react:

  • The content is obsolete or wrong: Add a note, mark it as outdated.
  • The commenter disclosed something secret: Replace the comment content with a note.
  • The commenter doesn’t want to be seen on the site anymore: replace the commenter name with anonymous.

In any case, I would require a reason for deletion request, and create a separate comment review queue. Use comment meta fields for that.