Then I created a couple of indexes: 1) CREATE INDEX idx_records ON fluent USING GIN (record);
What about using non-default jsonb_path_ops?
2) CREATE INDEX idx_btree_records ON fluent USING BTREE ((record ->> 'destinationServiceName'));
Is this key always set? If so, make it a proper column so you get statistics on common values and number of distinct values as such.
If it is rarely used, create a partial index perhaps. I am a little surprised that the plain btree index wasn't used from my naive point of view. Did you check execution time with sequential scan disabled to try to strongly encourage the use of index scan?