Why does "that" sound odd to me after "said" in these sentences with "as" and "like"?

You are reacting to stylistic expectations. That is optional in all four uses. As you add words that can also carry emphasis, it becomes more and more desirable to omit an optional element and thereby reduce the number of words that can be emphasized.

Martin Endley, in Linguistic Perspectives on English Grammar, has a section on optional "that clause complements":

Another striking feature of that clause complements when they function as DOs (direct objects) is that, under certain conditions, the use of the complementizer becomes optional and may be omitted without affecting the grammaticality of the sentence:

(53) a. Dr. Endley knows (that) Ankara gets very cold in the winter.

b. Dr. Endley told his mother (that) Ankara gets very cold in the winter. (p. 372)

What are the conditions of omission? Endley provides three general guidelines that guide usage:

1. Register. More formal utterances tend to use that, and spoken English is more likely to omit it.

2. The importance of information in the clause. If the information is more significant, that is more likely to be used. If the information is mostly descriptive, that is less likely to be used.

3. Distance between the main verb and the that clause. Close proximity renders the that-clause optional; with more intermediate phrases, the need to emphasize the relation to the main verb with a that-headed clause grows.

Guideline 2 is most relevant to your examples. In (1):

1. You said that he would come to the party.

The information is stated in full, and so it can be read as relatively significant. That gives an added bit of emphasis. However, in (4):

4. He came to the party, just like you said that he would.

"That he would" is the only part of the clause. The that-clause mainly acts to remind readers that you said information similar to the first part of the sentence. Because the information in this clause isn't otherwise significant, it feels odd to emphasize it with that. 2 and 3 follow similar lines: if 2 feels marginally acceptable, it is only because emphasizing that would be less odd without the added emphasis of just before like or as. In other words, at least in 2 that isn't competing for attention.

Source: Endley, Martin J. Linguistic Perspectives on English Grammar: A Guide for EFL Teachers. Information Age Pub., 2010.

Comments so far implied that the grammar was prinipally identical in all four examples. I disagree, and I would share the sentiment that the questionable examples are simply wrong, because the different sentence structure requires a different word order. This isn't clear cut, and from a descriptive perspective there's no wrong or right, as long as it's legitamte by virtue of common usage.

I simply reason that: In the more complex examples, if you preferentially expect the predicate to begin with the subject of the verbal phrase, then you will read "that" as a relative pronoun (rarely) or determiner "... just as you said that man would".

I'm not quite sure why it should differ in the former clause. I suspect it is because therein the main verb is in the matrix clause. In all other cases, the verb "say" is already in adposition. Maybe it could be said that it acts as conjunction itself, so no "that" is needed. This can be rectified by lifting the relative clause, just as you said it, that he would, which is more or less how it would be in German (genau wie du (es) gesagt hast, dass es passieren würde).

Consequently, we see a lot of that that, although the assumption about the origin of the conjunction is in fact from determinative usage, as far as I know.