Is it possible to create a rule-based algorithm to compute the relevance score of question-answer pair?
could we invent an algorithm like BM25 to compute the relevance score of question-answer pair? 


It depends:


BM25 (actually cosine with BM25 weighted vectors) is a simple similarity measure, ultimately based on counting words in common. Proposing a different similarity measure is easy, for instance there are various measures used for MT evaluation (including some quite sophisticated ones) which could be used as well. Of course, these measures don't actually measure the relevance, they just offer a crude approximation.
However if there was such a rule-based algorithm which would be able to actually measure the relevance of an answer in any context, then for all means and purposes we would have solved AI: judging the semantic relevance is much more subtle than counting words in common. In particular if there is such an algorithm, then the problem of question answering is solved: you can just generate all the possible answers and loop until one is found relevant to the question.


People have tried to do "intelligent" rule-based algorithms in NLP for decades, before realizing that ML is more efficient and performs much better in most tasks. So it's extremely unlikely that a rule-based algorithm would suddenly outperform ML on a non-trivial task like this.