Redmine

This all seems to be the expected behaviour. I'll elaborate based on your steps.

3. Click „Rename“ and move it to B.

By default, the checkbox for "Redirect existing links" is checked on the rename form. So, in this - default - case you tell Redmine to create a wiki-redirect like:

A - Wiki 'Start page'  --->>  B - Wiki 'Start page'

4. In A, click „Wiki“ tab. You're automatically redirected to Wiki of B. This is the first part of the issue.

This happens because of the wiki-redirect added in step 3. This can be changed however by unchecking the "Redirect existing links" checkbox. In that case the user won't be redirected and, with the permissions of project A, will be presented the editor to create the new page (if (which is in this case also the Wiki 'Start page').

5. Grant access to A to any user, but don't grant access to B. Now she will get 404 trying to view Wiki of A. This is the second part.

This happens - again - because of the redirect. If a redirect to another project exists for the wiki 'Start page', clicking the 'Wiki' menu item in project A will load the redirected page in project B. As such permissions of the user on project B will apply. If the user doesn't have the permission to view wiki pages of project B - the case in your scenario -, a 404 response will be served.

It seems that Wiki of A no longer exists. Turning Wiki module of A off and then on doesn't solve the issue. [...]

Well, if you move the wiki 'Start page' with a redirect to a page in another project (B), you are effectively shutting down access to project A's wiki. This is because the wiki 'Start page' is used as the target of the 'Wiki' project menu item. Without the redirect the editor shows up normally, indicating that the wiki exists and is activated.
Turning the Wiki module on/off won't do anything. It only disables the 'Wiki' project menu item for the project and disables rendering of any wiki page by returning 403 responses.

[...] Renaming the Wiki back to A works fine, but then there's no Wiki in B, and so on.

Well, you are not renaming the wiki page. You are actually moving the wiki page (to another project) using the rename form. This is by design (see #5450).
By moving a wiki page you actually move it (with its history). You don't make a copy. As such, a moved page will only exist in the target project after the move, leaving the base wiki page empty (this is why, if no redirect is added during the page move, your user would be presented with the editor to create a new wiki page in project A in step 4 - using wiki 'Start page' as the name for it - [note: only when the user has the 'Edit wiki page' permission on project A]).

Unfortunately, I don't know the exact version of Redmine I'm using, and have no privileges to discover it. I think it's relatively fresh, [...]

Looking at the history of the wiki page move feature, you are running either 3.0.x or trunk >= r13643.

I hope this sheds some light on the experienced behaviour. In my opinion everything works as expected. Can you provide some feedback? Thanks.

Regards, Mischa.