Is the usage "at" here proper?

Completely, but the present perfect is a wee bit strange, though possible, Ori.

Thanks.
How to improve, then?

====>>> To complete the job, we started work at eight o'clock.

Does the edited sentence sound natural?

Yes, that's more natural, Ori. There's a strong tendency for ENLs to avoid the use of the PP with a specific time reference. It's not, as I've mentioned, impossible, but that tendency is strong.