You've got a GREAT start to coding mod_rewrite but simply didn't translate your words into code properly.
# Check if xyz/ exists as xyz.pdf and redirect
RewriteCond /$1.pdf -f
RewriteRule ([a-z]+)/ $1.php [L]
# Note, this changes the directory level so you'll have problems with relative links
# Otherwise redirect xyz to page.php as the value of page
RewriteCond /$1.pdf !-f
RewriteRule ([a-z]+)/ page.php?page=$1 [L]
# Same directory level change so same problem
# That's why I loathe trailing /'s on filenames
Alternatively, MultiViews will attempt the first redirection for you automatically. MultiViews is a horrid function which, because it hijacks a directory name and attempts to serve a file, it causes major problems for the unsuspecting. IMHO, do it properly with mod_rewrite so you know everything that's going on with your redirections.
Oh, for your code:
# That should already be in the httpd.conf so it's redundant ([I]multiple times[/I] for EVERY request!)
RewriteRule ^([^/.]+)/$ $1.php [L]
RewriteRule ^([^/.]+)/$ page.php?page=$1 [L]
# If the first RewriteRule matches and redirects, how will the second RewriteRule ever match?
# Clearly it won't so the check on the existence of the file (with/without the .php extension)
# will separate the two rules.
ErrorDocument 404 /404.php
# Because mod_rewrite is not an Apache core module, it's always executed after all the core
# directives and modules (e.g., mod_alias) SO I group the core and core module directives
# at the top of my .htaccess file