Past participle
Solution 1:
Your examples are reduced relative clause constructions. "the table painted red" is from "the table which is/was painted red" by deleting the "which is" part. The deletion transformation has been called "WHIZ".
In turn, for this example, the "is/was" is part of a passive construction, the active form for which would be "someone paints/painted the table red". Whether the interpretation is present or past tense depends on the context the construction occurs in.