Let's suppose we shoot a piece of steel in space and after one billion year it splashes into an alien ocean. Natives take it ashore. Would they be able to understand that after all the exposure to radiation and possible collisions it's not only a lump of iron, carbon and a few other elements but something made by people somewhere else? Would it look like a normal meteor or its composition and structure is different?

Not an expert but I'm pretty sure it'd be easily identifiable as artificial because of the uniform composition and regular grain structure in steel. I think it would not only be clear that it was refined because of purity but also that it was far more regular than something natural. [1]

1. https://youtu.be/uG35D_euM-0

Some crystals are very regular.

https://en.wikipedia.org/wiki/Crystal#/media/File:Ho-Mg-ZnQu...

There might be a different isotope signature, that might give its origin away.

If it appeared worthy of analysis.

It will certainly look unusual. It's not clear to me that it will look artificial (we are pretty bad at deciding that one), but it won't look like anything else around it.