Can I create an approval rule for document records using flexfields?

Yes, you can using descriptive flexfields (DFF) and developer descriptive flexfields (DDF) in the Approval Setup tab in Transaction Console.

Note: The flexfield segments won't display the user configured segment names. You have to use the appropriate segment based on your flexfield configuration.