In the article, it says that 'The paper is made from elephant dung', not just infused with it. But in any case, you are right, that will kill the bacteria. The article doesn't contain any details on how the dung was treated, but they won't necessarily destroy the nutrient levels in the dung.
But as it is, you can do this with nutrient-sterile paper if you want, the fertilizer isn't necessary. In fact, this is a very common practice these days (I'm a gardener). You can easily buy seed tapes, or you can make them yourself.
And it does not need to be planted immediately, but won't last forever either. Every variety has different seed life expectations, so if stored in good conditions, refer to this convenient list of seeds and their longevity. Here is some information on the best storage methods for most seeds. For the question:
Furthermore is elephant dung in itself special?
I guess it could be called special in that it is not produced in quantity, compared to cattle or hogs, so it's not so common. Elephants also have a simple digestion system, so they don't digest their fibrous diet very well, similar to a horse, and the feces contain a good quantity of fiber. This makes the resulting feces very good as a paper substrate, and also makes it prime for garden use.
Because the elephant only digests and makes good use of 40% of its intake, the intestine is also instrumental in the formation or faeces and the efficient absorption of water. The size of the faeces is often used to determine the age of the elephant as it retains the shape formed by the walls of the rectum, indicating its size.
Because the elephant absorbs so few nutrients from the food it ingests, the dung is rich in nutrients and solid food matter. Therefore, it is beneficial to many other animals, as they are able to feed off of the relatively untouched constituents of the faeces. Common beneficiaries include dung beetles and many species of bird.
That explains why elephant dung is better suited to gardening paper than other manures would be. Usually the more simple the digestive system, the better the manure will be, in terms of nutrient content. (see example rating)