Prof. Yehudah Elitzur wrote an essay on the subject. In his view, the Amalekite wasn't the son of a convert or even a ger toshav, but an actual 100% Amalekite. What was he doing there? He was a spy. The Amalekites would send off Amalekite youths to collect information in preparation for the many raids the Amalekites did (consider how they first met Yisrael - raiding the people that lagged behind, raids in the time of Gidon, etc). After Plishtim defeated Shaul and Shaul killed himself, the Amalekite joined the Plishtim in pillaging the bodies. It seems he was the first to come upon Shaul's body and took from him his crown and band, and then decided to go to David, hoping for a reward and a chance to collect more info. According to Prof. Elitzur, David quickly discerned all of this. This understanding is based on the fact that first he attempted to present himself as an escapee from the battle:
"On the third day, a man came from Saul’s camp, with his clothes rent and earth on his head; and as he approached David, he flung himself to the ground and bowed low. David said to him, “Where are you coming from?” He answered, “I have just escaped from the camp of Israel.” “What happened?” asked David. “Tell me!” And he told him how the troops had fled the battlefield, and that, moreover, many of the troops had fallen and died; also that Saul and his son Jonathan were dead."
At this point, David already knew that the Amalekite was not one of the Israeli soldiers, because he then asked him:
"“How do you know,” David asked the young man who brought him the news, “that Saul and his son Jonathan are dead?”
This question should have been redundant, because if the Amalekite had looked like a soldier, David should have figured that he had been near the king when he fell (David had no idea at this point exactly how the king had died). However, it seems that the Amalekite's poor disguise (torn clothes and dirt on his head) was not enough; David recognized his clothes as being inherently/culturally Amalekite, so he pressed him to explain what he, a non-Israeli, was doing on the battlefield. And the Amalekite chose to admit that he indeed wasn't a soldier, nor even any sort of Israelite, by saying:
"The young man who brought him the news answered, “I happened to be at Mount Gilboa, and I saw Saul leaning on his spear, and the chariots and horsemen closing in on him...he asked me, ‘Who are you?’ And I told him that I was an Amalekite."
Later on, possibly for fear of what David might do to him, now that David figured out most of his story, he changed it again:
"David said to the young man who had brought him the news, “Where are you from?” He replied, “I am the son of a resident alien, an Amalekite.”"
According to Prof. Elitzur, David killed him because he was a spy who would potentially endanger Israel. However, he doesn't properly discuss why David would announce that he's killing him because "“How did you dare,” David said to him, “to lift your hand and kill the LORD’s anointed?”"
Therefore, it seems to me that perhaps the term "אֵיךְ לֹא יָרֵאתָ לִשְׁלֹחַ יָדְךָ לְשַׁחֵת אֶת מְשִׁיחַ ה'" has a different meaning than what is usually understood by it. "לשחת" means "to desecrate, spoil, pervert". I think David had two points folded into one:
a. That the Amalekite dared to desecrate one of Hashem's chosen - Shaul - by pillaging his body, which is major disrespect to any dead body, but is also a big disrespect to both Hashem and the Nation of Israel when it's done to the King of Israel.1
b. That the Amalekite dared to come to David - another of Hashem's chosen - with the intent of wreaking havoc upon David, his men and all of Israel by passing off misinformation and at the same time, gathering key information and passing it on to the Amalekites.
For these reasons - being that he both desecrated an important symbol of Israel - the king - and that he posed a real geopolitical threat to Israel (din rodef at the very least), he was killed.
1 I should note that at this point, David had likely also figured out that the Amalekite hadn't really killed Shaul, because the Amalekites had brought upon the start of his downfall. Shaul would have never begged an Amalekite of all people to end his life. This also explains the end of the story, in which David says: "And David said to him, “Your blood be on your own head! Your own mouth testified against you when you said, ‘I put the LORD’s anointed to death.’”" - his story was so full of holes that that is what brought his death.