(a) It is only when a Dibur has an outcome similar to that of a physical act that it is considered a Ma'aseh, with regard to Malkus. Relating false testimony, as prohibited in the Lav of Lo Sa'aneh, involves mere speech. (That is, nothing has been accomplished by the speech.) That is what the Gemara in the beginning of Makos means when it says that false testimony involves no Ma'aseh. (That does not mean that it is not a sin , of course; it is just not punishable with Malkus.)

(b) Your question from the Gemara in Bava Kama, though, is a good one. Why does the Gemara not say that we learn from "Ka'asher Zamam La'asos" that the Torah calls what an Ed Zomem does, a Ma'aseh? (Your question can also be asked on the Gemara in Kerisus (4b), which says that Edim Zomemin is considered a "Lav she'Ein Bo Ma'aseh" such that the transgressor does not bring a Korban Chatas.) Indeed, the NETZIV asks this question in Bava Kama (4b). Tosfos in Shevu'os (21a, DH Chutz) also points out the apparent contradiction between the Sugyos in this regard, but he does not explain how they in fact can be reconciled (see there, and see ARUCH LA'NER in Makos 4b).

It appears that the distinction is as follows. The intention of the Gemara in Bava Kama is that the witnesses caused a Ma'aseh to be accomplished (by others) as a result of their testimony -- that Ma'aseh being the Gemar Din of Beis Din. This is clear from Tosfos in Sanhedrin (65a, DH Ho'il), who writes that Edim Zomemim is considered more of a Ma'aseh than other sins involving speech since through the false testimony the defendant was found guilty (see also Or Same'ach Hilchos Edus 18).

This is what the Gemara means in Bava Kama 4b when it states that because Edim Zomemim "involves a Ma'aseh," it is fitting to be mentioned among the list of Avos Nezikin (in contrast to a Moser). The verse of "La'asos" was cited there only in order to show that when the defendant becomes Chayav due to the witnesses' testimony, it is considered to be a direct result of their testimony. It is not comparable to damage (Hezek) caused by a Moser, for such damage does not come about as a direct result of his words, but rather through the fact that a Nochri heard his accusation and acted upon it.

On the other hand, the witnesses themselves certainly did no Ma'aseh but only spoke, and therefore they cannot receive Malkus nor bring a Korban Chatas, as the Gemara explains here and in Sanhedrin 65a and Kerisus 4b (where the Gemara says "Edim Zomemim is not a Ma'aseh because Yeshnam b'Re'iyah," see Rashi and Rishonim there).

(c) Another answer to your question can be found in the Megilas Setarim of Rav Nisan Ga'on (cited by the Margoliyos ha'Yam in Sanhedrin 65b, #8) who has -- in Kerisus and Sanhedrin -- the Girsa that "Edim Zomemim is different (and is not considered a Ma'aseh) because Yeshnam b'Im ." One explanation he offers for this Girsa is that even though the speech of Edim Zomemin is considered like a Ma'aseh because the verse writes, "Zamam La'asos " (as you cited from Bava Kama 5a), nevertheless, since the verse has to write "v'Hayah Im Bin Hakos" (this is the "Im" to which the Gemara there is referring) in order to be Mechayev Edim Zomemim Malkus, as our Gemara (Makos 2b) teaches, this implies that the Torah does not consider Edim Zomemim enough of a Ma'aseh to obligate a person in Malkus or a Korban without an explicit verse.

According to his words, Edim Zomemim is in fact called a Ma'aseh by the Torah on the one hand, and nevertheless it is excluded by another verse ("v'Hayah Im Bin") from being considered enough of a Ma'aseh to obligate one in Malkus or a Korban.

It is possible to explain in such a manner even according to the Rishonim who do not have the Girsa of "Yeshnam b'Im," but "Yeshnam b'Re'iyah." "Yeshnam b'Re'iyah" might simply be a logical justification for why the Torah does not consider Edim Zomemim enough of a Ma'aseh to obligate a person in Malkus or a Korban without an explicit verse.

M. Kornfeld