What is the difference between the following sentences?
He went up to the table to grab some cake.
He went over to the table to grab some cake.
If the phrases have identical meanings, could the verb come be used with the same meaning?
I think that the answer to both questions is yes. There may be a very subtle difference in that to "went over to" implies that the table and the man were on the same level either socially or physically, for example at a party where he was a guest. On the other hand "went up to" could imply that the table was somehow special or appart, for example "went up to the table to receive a prize from a VIP". Nevertheless, in your example either works.
You can substitute "came" for "went" with almost identical meaning. Again the only difference may be that "came" implies he approached the table whilst "went" implies he left wherever he was in the direction of the table. The same action from two different points of view.
However I don't think anyone would object if you used any of the 4 possible forms, they are very close in meaning and all would understand what you meant as my comments are not hard and fast rules.