A federal judge ordered Microsoft Corp. to pay Alcatel-Lucent $511.6 million in damages and interest, letting stand a jury’s decision that the software maker infringed on two patents.

Microsoft vowed to appeal the decision, which marked the latest move in a 5-year-old patent scuffle between the two companies.