It looks like your perl code just concatenates the data with the salt, then hashes that - a4584f550a133a7f47cc9bafd84c9870
is simply the MD5 of "HelloWorld" + "12345678"
.
Rather than using HMACMD5, you just need to do something like this, using MD5:
using (MD5 a = MD5.Create()) {
byte[] bytes = Encoding.UTF8.GetBytes(data + salt);
byte[] hashed = a.ComputeHash(bytes);
var sb = new StringBuilder();
for (int i = 0; i < hashed.Length; i++) {
sb.Append(hashed[i].ToString("x2"));
}
Console.WriteLine(sb.ToString()); // a4584f550a133a7f47cc9bafd84c9870
}