*Not a Teacher*
There is no difference in meaning between those sentences. Also, neither of the statements give any indication as to when the payment will be made.
"They" is the subject of the sentence.
For the first sentence, I would write this:
"They decided to pay for the construction of a new monument."
For the second:
"They decided to pay to have a new monument constructed."