If an employee works overtime (and gets paid for it), how does this affect a nation's GDP? GDP = Consumption + Government Expenditure + Investment + Exports - Imports

My cases are:

(1) If the employee is getting paid for his extra-work, his consumption would increase.

(2) This employee might take away the job of someone else --and thus his increase in spending could get nullified

By  definition, GDP = the total value of all goods and services produced. 

(1) If even after working overtime, the company produces the same amount of goods / service --by definition, GDP hasn't risen at all.
You are correct: an increase in the wage does not by itself imply an increase in GDP. So, if you pay a worker \$20 for an hour of overtime which you could have bought from another worker for \$10, but they both produce the same thing, GDP does not change by switching from one arrangement to the other.

You can also observe that from the 'income perspective' in the circular flow of the economy: if nothing else changes, a higher wage for a  worker results in lower profits for the firm, but the net effect on income is 0.

However, a change in which hours are labeled as overtime and which are not could have important effects in the economy. You'd expect that on average firms will prefer to have relatively more workers working relatively few hours and so avoid paying overtime. This should increase employment, but not average worker income, it should reduce inequality among workers, etc. 

Potentially there can be large effects are on the health insurance costs of firms of changing overtime laws.