We usually say "decide to do sth" rather than "decide and do sth." "decided" is then the main verb in your sentence. Also, I don't think the king built the shrine himself! At most, he had it built.
That said, we have at least two possible passive versions for your sentence:
3) Over 2500 years ago, (under the reign of King Okkalapa,) the decision was made (by King Okkalapa) to build a shrine on Singuttara Hill. (You have to choose just one of the phrases between parentheses -- only the second one indicates that it was the king who made the decision.)
4) Over 2500 years ago, (under the reign of King Okkalapa,) it was decided to build a shrine on Singuttara Hill.
To tell you the truth, I like (3) better than (4).