Since you're asking a question about the value-added approach to calculating GDP, the answer that follows talks about the value-added approach. It's worth noting, however, that GDP can (and is) also calculated through two other approaches: the expenditure approach and the income approach. In the US, the value-added approach is used primarily in the GDP-by-industry accounts.
The boundary between intermediate and final consumption seems blurry. How, and where is the line drawn?
Products and services provided to consumers are considered to be final products. Products and services provided to businesses are treated as intermediate inputs. See point 4 on page 3 in this NIPA primer.
When doing the accounting at an high level (city, state or national), how do the accountants know what part of the paint consumed take as intermediate consumption and what part to take as final consumption?
A simplified answer (ignoring issues like capital consumption and inventories) is that at the national level, business revenue is totaled, and then business expenses (other than labor costs) are subtracted.
So if a restaurant sells \$100 worth of dinners, pays a farmer \$50 for the food, and pays a designer \$10 for designing the restaurant, the totals look like this:
Restaurant: \$100-(\$50+\$10)=$40
Designer: \$10
Farmer: \$50
Total: \$40+\$10+\$50 = \$100
As you can see in this example, by subtracting business expenses from revenue, double-counting is eliminated.
At the state level in the US, GDP is actually allocated from the national level using a variety of techniques. Metro area GDP is allocated from the state level to counties based on income by industry and then aggregated. As a result, the value-added approach is simply not used to calculate state and local GDP in the US.
Is the service of cleaning a factory considered a final product or intermediate consumption needed to produce whatever the factory produces?
Intermediate consumption.
What about the plant's paint, electricity, training of workers and so on?
Intermediate consumption.
The consumption of decoration from a restaurant is a requirement (since people go to a restaurant in part, due to the style) and by that reasoning, it is intermediate consumption, but a luxury in one's house (therefore final consumption).
Intermediate consumption.
People need to eat in order to work and produce, and more so the more they work (hence food may be classified as intermediate consumption), and need medical care to live (and hence produce) just like car factories need steel. I have seen these things sometimes taken to be final consumption.
If you refer to the example above, you will see why they're treated as final consumption. The household sector is not treated as a business; if it were, the value-added approach would not work. Wages paid to workers would be subtracted as intermediate inputs, and workers' consumption of whatever they consume would also be subtracted as intermediate inputs, and everything would sum to zero.
If a restaurant sells \$100 worth of dinners, pays a farmer \$50 for the food, pays a designer \$10 for designing the restaurant, and pays workers \$20 for making the food, the totals look like this:
Restaurant: \$100-(\$50+\$10+\$20)=$20
Designer: \$10
Farmer: \$50
Households: \$20-\$100=\$-80
Total: \$20+\$10+\$50-\$80 = $0
What we've discovered above is called the circular flow of goods and services.
A simpler example can make this obvious: let's say that there exist two businesses in an economy. One grows cabbage, the other raises pork. The cabbage guy gets hungry for some pork, and buys \$10 worth of pork, while the pork guy decides he wants some cabbage and buys some of that for \$10. Under the value-added approach, \$20 of market output has been produced. If we said, "Hey, wait, but people need to eat food to live!" and did not count the food production, then we'd end up concluding that \$0 of market output had been produced. That would be incorrect.
