Were Anahita and Mithra already popular (including among the royalty) when Artaxerxes II started the practice? What did worship of these three look like in terms of practice?
Religion is perhaps the most hotly and consistently debated question in Achaemenid studies. No one answer is ever going to satisfy every potential interpretation of the extremely scant and fragmentary evidence. To make matters worse, the bulk of that evidence is both foreign and post-Achaemenid and thus likely to retroactively project later Iranian beliefs and practices back on to the earlier period through a highly filtered Greek lens. Even accounting for that, it's impossible to satisfy every scholarly opinion. So with that disclaimer, I'll give it a shot.
Given how complex a topic we're looking at, and the amount of context I expect most AskHistorians readers will need for topics like Zoroastrian divinities and Elamite mythology, this is going to be a long one.
Between Darius and Darius II, Achaemenid inscriptions only invoke Ahura Mazda by name.
"Achaemenid inscriptions" and "by name" are both very important qualifiers here, whether intentionally or not. In several inscriptions, Darius the Great refers to other gods generically, either as "all the gods there are" (Behistun Inscription lines 62-63) or simply "gods" as well as "gods of the royal house" (Inscription DPd). Outside of monumental inscriptions, at least 18 deities are identified by name in the administrative records of Achaemenid Persepolis and Susa. Some of these were existing Elamite gods that predated the arrival of Iranian peoples in the region by millennia and can simply be attributed to the general Achaemenid practice of patronizing local religion in every part of the empire. However, roughly half of the deities referenced at Persepolis are Iranian divinities, largely familiar names to anyone who has read the Zoroastrian Avesta, but at least two not attested outside of the Achaemenid context.
Interestingly, neither Mithra nor Anahita appear in these records, which can give the false impression that they were not significant in Darius the Great's time. This in undoubtedly untrue, at least for Mithra.
Were Anahita and Mithra already popular (including among the royalty) when Artaxerxes II started the practice?
Well, to start, I actually want to point out that while he was obviously the preferred deity of the Great Kings, Ahura Mazda himself was only the second most popular deity even in the Persian home province based on the surviving Persepolis Fortification Archive tablets. The top spot actually goes to Humban, the Elamite king of the gods. In fact, the two were often honored in the same annual events. This is probably more reflective of the continuation of Elamite culture in historically Elamite territory than anything else, but still worth acknowledging.
Mithra had been a popular deity among the Iranian peoples since before there were distinct Iranians. He's one of the few major deities to feature prominently in both the Indian Vedic tradition and Iranian Zoroastrianism. These linguistic-religious categories broke off from one another around 1500 BCE, and there's nothing much to suggest that Mithra's popularity ever waned significantly in Iranian belief thereafter. In fact, there is slightly more to suggest that the prophet Zoroaster may have tried to de-emphasize Mithra and most of the pantheon in favor of Ahura Mazda and the six Amesha Spentas c.1200-1000 BCE. Only those seven divinities are mentioned by name in the Gathas, the oldest part of Zoroastrian scripture attributed to the prophet himself.
Take that with a grain of salt though. The Gathas do reference the vague concept of other good spirits beside Ahura Mazda, and its unclear whether they are intended to be the six Amesha Spentas or the other divinities like Mithra. Within a century or two of Zoroaster's time, it's generally accepted that Mithra was very popular in Zoroastrianism. The Mihr Yasht, a prayer dedicated to Mithra, is among the oldest post-Gathic parts of the Avesta.
That said, there is a tendency in older Achaemenid scholarship to overemphasize the importance of Mithra with grandiose claims that he was actually the chief deity of the Medes and Persians before Darius the Great emphasized Ahura Mazda. There is simply no evidence at all for this, and the flimsy sources usually used to support the claim is heavily reliant on the long-discarded theory that Zoroaster lived in the early Achaemenid period (apx. 600 years after the commonly accepted dating).
However, Herodotus may be more useful for understanding the early popularity of Mithra and his association with an Anahita-like goddess in the Achaemenid period. His understanding of Persian traditions was usually flawed at best, but the description of Persian religion in 5th Century Anatolia is noteworthy:
...they call the whole circuit of heaven Zeus, and to him they sacrifice on the highest peaks of the mountains; they sacrifice also to the sun and moon and earth and fire and water and winds. From the beginning, these are the only gods to whom they have ever sacrificed; they learned later to sacrifice to the “heavenly” Aphrodite from the Assyrians and Arabians. She is called by the Assyrians Mylitta, by the Arabians Alilat, by the Persians Mitra. (1.131.2-3)
Ahura Mazda is routinely identified as Zeus, and the first half is not totally accurate to Zoroastrian theology, but close enough for an outside observer. The second half however erroneously identifies "Mitra" with a series of Near Eastern goddesses typically compared to Anahita. The confusion over the name is clearly indicative of the fact that already in the mid-5th Century, Iranian settlers in the western Empire were treating Mithra and this goddess as a pair. The fact that Herodotus makes a distinction between the goddess and earlier Persian traditions is also noteworthy, as it implies that she was worshipped in what he considered the more conventional method of an idol inside a physical sanctuary.
Both Mithra and Anahita were subject to comparison/conflation with other gods, as seen in the quote from Herodotus. Mithra is often described as heavily armed and his name literally means "oath," so he was quickly compared to the Mesopotamian and Elamite god Shamash, likewise a warlike patron of oaths. Shamash was also the god of the sun, a feature not associated with Mithra in the earliest Indo-Iranian evidence, but something he took on in the Achaemenid period or shortly before.
The epithet Aredvi Sura Anahita (Wet, Powerful, Pure) is applied to an unnamed goddess of waters in the Aban Yasht. Over time, the title Anahita replaced the original name and Aredvi Sura became an epithet for the name "Anahita." Like the hymn to Mithra, this is a very ancient Zoroastrian prayer, but unlike Mithra, there is not substantial evidence that Anahita was of paramount importance early on. Instead, her genesis is tied closely to an interconnected series of Elamite and Mesopotamian goddesses centered on the Babylonian Ishtar, a goddess of warfare, love, and fertility.
The Elamite goddess Narundi (mythologicaly the wife of Nahunte, a near 1:1 comparison with Shamash), patron of motherhood and protector from illness. That made her an easy comparison to the Sumerian goddess Inananna, goddess of love, who was in turn compared to the Akkadian Ishtar. But Ishtar also had elements of a warrior goddess. Slowly but surely, Narundi’s role of protector from illness became goddess of victory in all struggles. In Assyria, Ishtar was identified with Mulissu, Herodotus' Mylitta. Likewise there is a connection to the Arabian Alilat, though more complex.
Meanwhile, another Sumerian goddess called Nanaya was also a goddess of love and conflict, but remained popular enough to have her own cult alongside Ishtar even though the two were commonly grouped together. Nanaya became very popular in Susa as a second comparison to Narundi and eventually the name Nanaya supplanted Narundi and took on aspects of Ishtar more directly in Susa than she actually did in Mesopotamia. At the same time, another Elamite goddess called Kiririsha was a war goddess, but also a sort of mother Earth figure alongside her divine partner, Napirisha, a god of the primordial waters and creation of the mortal world.
Kirisha was distinct enough not to get absorbed into the Ishtar-Narundi-Nanaya mess in the Neo-Elamite period, but when Iranians showed up worshipping a goddess of love, sex, and primordial waters called Anahita she absorbed aspects of Elamite Nanaya and Kiririsha, taking on that warrior goddess flavor too. Nanaya and Anahita actually became so interchangeable that Nanaya wound up the preferred name for Anahita in Bactria, all the way in modern Afghanistan. The problem for identifying the goddess behind Herodotus' "Mitra" is that we do not know where Anahita was in this process at the time, and unfortunately the first major study on that topic, "The Other Gods Still Are" by W.F.M Henkelman is still awaiting publication.