Is it possible to append new blocks to a block of arbitrary age? First of all, I'm aware of 51% attacks and how they work.
Though, I was wondering, if Bitcoin and other blockchains allow appending cryptographically valid, new blocks to blocks of arbitrary age (if no age restriction is in place).

For example, could I simply append a new block to the genesis block or are there any other restrictions than just the validity of the block itself?
And if this is the case, would the "Bitcoin network" really accept a completely new blockchain starting from the genesis block, if I really managed to make a blockchain with higher difficulty, than the current chain? (Like a 99,999% attack :) )
For example, could I simply append a new block to the genesis block


Yes, you can. You can actually do this if you start your node offline and begin mining.


  or are there any other restrictions than just the validity of the block itself?


There are, but only for legacy reasons. There are a set of checkpoints where, at a specified height, the block must have a specific hash. These were added to provide a performance boost, but have the side effect of locking in the blockchain to specific blocks. The most recent checkpoint is at block 295000. So unless you are able to find blocks that have the same hash at all of the checkpoints, you actually cannot produce an entirely different blockchain and have the Bitcoin network accept it.


  And if this is the case, would the "Bitcoin network" really accept a completely new blockchain starting from the genesis block, if I really managed to make a blockchain with higher difficulty, than the current chain? (Like a 99,999% attack :) )


If you were able to produce such a blockchain and produce blocks which have the correct checkpoint block hashes (or if you forked the blockchain after the most recent checkpoint), then yes, the Bitcoin network would accept your alternative blockchain as it has more work.