despite is a preposition meaning not prevented by. A preposition normally attaches a noun to a sentence, for example:
He completed the marathon, despite his age.
already having paid the money is a noun phrase. We can include a verb in a noun phrase using either a gerund or an infinitive: in this case, a gerund is used. We make the present form of a gerund by putting -ing on the end of the verb- this is quite common- but we can also make the past gerund form by putting having in front of the perfect form- thus, having paid.
The main verb in the sentence is was, which is past simple. The strange bit in this sentence is the perfect form of the gerund, having paid.
There are fewer opportunities to use the past form of a gerund than the present form, and in addition, according to this NGram, its usage has declined steadily over the past 200 years.