Panini's grammar is said to have algebraic rules governing every aspect of the Sanskrit language. If the rules are completely formal, what is the place of this grammar in the Chomsky hierarchy? How come a natural and complex language can have a formal grammar? What makes Sanskrit exhibit this rare (unique?) feature among natural languages?
This page explains the concept of "regular expression". Also note this discussion of "regex" features available in e.g. Word's regex search and replace function, which are beyond what are defined for "regular expressions". For example "a string beginning with any of [aeiou] which is terminated by the same letter", which is beyond what constitutes a regular expression. A "regular grammar" uses only regular expressions. For the sake of clarity, a "regular language" would be a language that can be generated using only regular expressions. Another kind of expression is "unrestricted rewrite rule" or "Turing machine", which can do anything that can be called a computer algorithm.
Panini's grammar is available here, with links to the individual chapters. What is provided there is an augmented version of the Astadhyayi, an English translation with commentary. The first rule say "vṛddhirādaich", which is a rule defining [ā au ai] as having the property "vṛddhi". And so forth. Rule 6.1.77 says "ikoyaṇaci", which translates to "of [i u ṛ ḷ ] [y v r l] before vowels". The rules of the grammar must also be interpreted by rules of the grammar to make sense – in this case, the rules omit some things that can be supplied by rule, and a more verbose version would be "in the place of [i u ṛ ḷ ] there is, respectively, [y v r l] before vowels, in connected speech". The Paninian system is very complicated, and exceeds what constitutes a system of regular expressions, possibly going beyond finite state grammar (see this article). While it is possible to model "respectively" in a system of regular expressions, [a,b,c...e] → [A,B,C...E] respectively goes beyond regular expressions in the Chomsky hierarchy sense. You should also note that the Chomsky hierarchy is based on a particular set of mathematical principles that encompass everything that can be called a computation. Wherever the Ashtadhyayi sits on this hierarchy, there will be devices that do more than Panini's grammar does, so there is nothing in the grammar/device taxonomy that exactly describes Panini's grammar.
The popular language-learning notion of "regular" is completely different, and seems to be more based on learning a "base form" such as the infinitive or nominative, then applying simple rules like "replace -ein with -o: to form the 1st singular". Linguistic grammar take a completely different view, relying on abstract underlying forms and sets of rules that don't just say how to convert one surface form to another form. Panini's rules are of the same abstract type as are found in linguistic grammars.
The following paper by Penn and Kiparsky specifically addresses your question:
Penn, Gerald, and Paul Kiparsky. "On Panini and the Generative Capacity of Contextualized Replacement Systems." Proceedings of COLING 2012: Posters. 2012.
A link is provided on Kiparsky's website: https://web.stanford.edu/~kiparsky/Papers/panini-1.pdf
Basically, the form of a standard operational rule (vidhi sutra) in Panini's grammar looks like a context-sensitive rule. However, it does have a constraint on cyclicity which reduces its complexity. This constraint is not that there can be no cyclic applications of rules, which would generate regular languages, but a slightly weaker constraint the authors of the paper call "Nilakanthadikshitar's condition" (after the classical author that gives a statement of it) that prevents cyclic application of rules where a context is reused. The authors develop a more precise understanding of this idea of reusing a context and explore what this entails about the complexity of the resulting system and where it fits in Chomsky's hierarchy.
In brief, the authors argue that (from their abstract) "The formalism behind Paninian grammar, in fact, generates string languages not even contained within any of the multiple-component tree-adjoining languages, MCTAL(k), for any k."