Complete htaccess solution for modern URL rewriting (language in path, allow parameters, convert old links, etc.)

I'm currently optimizing an old website. For the sake for SEO and a modern user experience I'd like to convert all links using htaccess. I thought it's going to be an easy task as a lot of users already did this but I've only found very short examples covering only a small part of the whole task. Trying to combine some parts and extenting them myself I got really frustrated. I hope you can help me out...

Given (current links are in the following form):

/index.php?page=contact
/index.php?page=contact&lang=en
/index.php?lang=de&page=contact&sth=else&val=1#section
/?page=contact

Desired new URL form:

/en/contact
/de/contact?sth=else&val=1

---

What I came up with so far:

RewriteEngine On
RewriteBase /

# Remove trailing slash
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule ^(.*)/$ /$1 [L,R=301]

# Redirect only if no language provided
# Test for known languages and fall back to English
RewriteCond %{HTTP:Accept-Language} ^de [NC]
RewriteRule ^$ /de/ [L,R=301]
RewriteCond %{HTTP:Accept-Language} ^fr [NC]
RewriteRule ^$ /fr/ [L,R=301]
RewriteRule ^$ /en/ [L,R=301]

# If provided language is unknown redirect to English; 
# The following doesn't work. May it's better to do this in index.php?
#RewriteCond %{REQUEST_URI} !^/(en|de|fr)/?
#RewriteRule .* /en/ [R,NC,QSA]

# Load default start page if no other assigned
RewriteRule ^([a-z]{2})$ $1/home [R,L]

# Language and page assigned
RewriteRule ^([a-z]{2})/([a-z0-9_-]+)$ index.php?lang=$1&page=$2 [L,NC]

---

This seems to work quite well already. However, as soon as I've tried to add the following requirements as well, I only broke it.

1.Calling a page in the old format needs to be transformed to the new format so old/external links aren't broken. Whatever I've tried I only created endless loops.

/index.php?page=contact -> /en/contact
/index.php?page=contact&lang=de#section -> /de/contact#section
/?lang=fr -> /fr/home

2.If there's no language or an unknown language, it needs to fall back to the preferred browser language (if supported, like de or fr) or English.

/xx/contact -> /en/contact
/contact?val=1#section -> /en/contact?val=1#section

3.I'm not sure what to do with image/css/JS paths. Most of them are currently implemented in HTML as src="images/i.jpg". Is it better to convert them all to src="/images/i.jpg" or to add another htaccess rule so that a path like /en/contact/images/i.jpg gets the image correctly?

I hope you can help me out on this. Also I believe this is a common case so the result might be a complete solution for other people as well. Thank you.