How to find out which host / IP address / program performed a delete?
You will not be able to find this information after the fact. You'll need to add a trigger and a logging table (or set up an expensive server-side trace, or add manual logging to your data access methods).

Here is a very quick example of how to implement a logging table and a trigger:

CREATE TABLE dbo.TableNameDeleteLog
( 
  PK_From_TableName INT,
  Program NVARCHAR(128),
  Host NVARCHAR(128),
  IP VARCHAR(48),
  When DATETIME NOT NULL DEFAULT CURRENT_TIMESTAMP
);
GO

CREATE TRIGGER dbo.LogDelete_TableName
ON dbo.TableName
FOR DELETE
AS
BEGIN
  SET NOCOUNT ON;

  DECLARE @p NVARCHAR(128), @h NVARCHAR(128), @i VARCHAR(48);

  SELECT @p = s.host_name, @h = host_name, @i = c.client_net_address
    FROM sys.dm_exec_sessions AS s
    INNER JOIN sys.dm_exec_connections AS c
    ON s.session_id = c.session_id
    WHERE s.session_id = @@SPID;

  INSERT dbo.TableNameDeleteLog(PK_From_TableName, Program, Host, IP)
    SELECT PK_Column, @p, @h, @i
    FROM deleted;
END
GO