I ran pdfmark you provided with 9.10's pdfwrite device without error, but 9.00 fails with the same message as you show.
Update: Assuming, that page labels you need are 1,1,2,3...3261 (don't know why, but that's what is in your example), it's simpler to add auto-incrementing numeric labels, not string prefixes as you do.
[{Catalog}<<
/PageLabels<</Nums[0<</S/D>>1<</S/D>>]>>
>> /PUT pdfmark
Or, if prefixes are what's necessary, split your big array into two or more:
[/_objdef{leaf1}/type/dict/OBJ pdfmark
[/_objdef{leaf2}/type/dict/OBJ pdfmark
[{leaf1}<</Limits[0 3000]
/Nums[
... 0 to 3000 labels go here ...
>>/PUT pdfmark
[{leaf2}<</Limits[3001 3261]
/Nums[
... 3001 to 3261 labels go here ...
>>/PUT pdfmark
[{Catalog}<</PageLabels<</Kids[{leaf1} {leaf2}]>>
>>/PUT pdfmark
Both these solutions work with 9.00