How can I found it an Item was replace on a Purchase Order or if it was removed and a new line for a different Item was created?

Every line has a History link you can review for changes made to that specific line

If it was removed and a new line for a different item was created? I'm also curious on how to track this. The new item does not have a link to the deleted line, so I don't know how to figure that out.

If $$ are involved you can look at the master system information on the Total field.

Now that I look at it in detail, I believe a PO line was deleted. Does NS has anything that shows the deleted PO lines?